문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

# 1963
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 1. 소수 판정
# 2. 소수 변환

prime = [True] * 10000

for i in range(2, 10000):
    if prime[i] == False:
        continue
    for j in range(i*2, 10000, +i):
        prime[j] = False

        
def count(n, num):
    global prime, time
    if num < 1000 or num > 9999 or prime[num] == False:
        return False
    if time[num] == - 1 or time[n] + 1 < time[num]:
        time[num] = time[n] + 1
        return True
    return False


def bfs(n):
    global prime, k, time
    queue = deque()
    queue.append(n)
    time[n] = 0
    
    while queue:
        n = queue.popleft()
        
        if n == k:
            continue
        
        numbers = [(n%1000, 1000), ((n//1000)*1000+n%100, 100), ((n//100)*100+n%10, 10), ((n//10)*10, 1)]
        for i in range(10):
            for num, j in numbers:
                x = num + i * j
                if count(n, x):
                    queue.append(x)

                    
t = int(input())
for _ in range(t):
                    
    n, k = map(int, input().split())
    if n > k:
        n, k = k, n
    time = [-1] * 10000

    bfs(n)

    if time[k] == -1:
        print("Impossible")
    else:
        print(time[k])

백준 1963 소수 경로