from collections import deque
p = [-1, -1] + [0] * 9998
prime = []
for i in range(2, 10000):
if p[i] == 0:
prime.append(i)
for j in range(2*i, 10000, i):
p[j] = -1
def sosu(a, b):
check = [-1] * 10000
q = deque()
q.append(a)
check[a] = 0
while q:
x = q.popleft()
if x == b:
return check[b]
u = int(x/1000)
v = int(x/100)-(10*u)
z = x % 10
w = int((x%100 - z)/10)
y_list = []
for i in range(1, 10):
y_list.append(i*1000 + v*100 + w*10 + z*1)
for i in range(0, 10):
y_list.append(u*1000 + i*100 + w*10 + z*1)
y_list.append(u*1000 + v*100 + i*10 + z*1)
y_list.append(u*1000 + v*100 + w*10 + i*1)
for y in y_list:
if check[y] == -1 and (y in prime):
q.append(y)
check[y] = check[x] + 1
return check[b]
t = int(input())
for test_case in range(t):
a, b = map(int, input().split())
ans = sosu(a, b)
if ans == -1:
print('Impossible')
else:
print(ans)
에라토스테네스 체로 소수를 모두 구한 후 -> 한자리씩 1-9 또는 0-9 를 바꿔 넣어서 bfs