이번 문제는 BFS와 에라토스테네스의 체를 이용하여 해결하였다. 우선 4자리 수에 대한 소수 정보를 담은 primes 리스트를 만들기 위해 에라토스테네스의 체를 이용하였다. 그리고 BFS를 통해 주어진 4자리 수를 바꿀 수 있는 모든 경우를 탐색하며 primes리스트 상에서 소수로 정의되어 있는지, 방문된 수인지를 확인하게 하였고, 이를 모두 만족하는 경우에만 다음 탐색을 계속 진행하여 목표 수에 도달하면 카운팅 변수를 반환하고, while문이 끝날 때까지 반환되지 않았다면 Impossible을 반환하도록 하였다.

Code

import math
from collections import deque
t = int(input())
primes = [True for _ in range(10000)]
def make_primes():
    for i in range(2, int(math.sqrt(10000))+1):
        if primes[i]:
            for j in range(i+i, 10000, i):
                primes[j] = False
def change_pw(start, end):
    q = deque()
    q.append((start, 0))
    visited = [False for _ in range(10000)]
    visited[int(start)] = True
    while q:
        cur, cnt = q.popleft()
        if cur == end:
            return cnt
        for i in range(4):
            for j in range(10):
                if i == 0 and j == 0:
                    continue
                nxt = cur[:i]+str(j)+cur[i+1:]
                if primes[int(nxt)] and not visited[int(nxt)]:
                    visited[int(nxt)] = True
                    q.append((nxt, cnt+1))
    return 'Impossible'
make_primes()
for _ in range(t):
    a, b = map(str, input().split())
    print(change_pw(a, b))