You are given two four digit prime numbers Num1 and Num2. Find the distance of the shortest path from Num1 to Num2 that can be attained by altering only single digit at a time such that every number that we get after changing a digit is a four digit prime number with no leading zeros.
 
Example 1:
Input:
Num1 = 1033 
Num2 = 8179
Output: 6
Explanation:
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179.
There are only 6 steps reuired to reach Num2 from Num1. 
and all the intermediate numbers are 4 digit prime numbers.
 
Example 2:
Input:
Num1 = 1033 
Num2 = 1033
Output:
0
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve() which takes two integers Num1 and Num2 as input parameters and returns the distance of the shortest path from Num1 to Num2. If it is unreachable then return -1.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
1000<=Num1,Num2<=9999
Num1 and Num2 are prime numbers.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Number theory

Graph traversal

Shortest paths

Starter code: #User function Template for python3

class Solution:

    def solve (self,Num1,Num2):

        #code here





Solutions:
from math import sqrt

class Solution:

	def is_prime(self, n):
		for i in range(2, int(sqrt(n)) + 1):
			if not n % i:
				return False
		return True

	def solve(self, Num1, Num2):
		data = [False for i in range(10000)]
		visited = [False for i in range(10000)]
		output = []
		for i in range(1000, 10000):
			if self.is_prime(i):
				data[i] = True
				output.append(i)
		adj = [[] for i in range(10000)]
		for t in output:
			(a, b, c, d) = map(int, list(str(t)))
			for i in range(1, 10):
				if i != a and data[1000 * i + 100 * b + 10 * c + d]:
					adj[t].append(1000 * i + 100 * b + 10 * c + d)
			for i in range(10):
				if i != b and data[1000 * a + 100 * i + 10 * c + d]:
					adj[t].append(1000 * a + 100 * i + 10 * c + d)
			for i in range(10):
				if i != c and data[1000 * a + 100 * b + 10 * i + d]:
					adj[t].append(1000 * a + 100 * b + 10 * i + d)
			for i in range(10):
				if i != d and data[1000 * a + 100 * b + 10 * c + i]:
					adj[t].append(1000 * a + 100 * b + 10 * c + i)
		q = [Num1]
		visited[Num1] = True
		ptr = 0
		level = 0
		while ptr < len(q):
			if q[ptr] == Num2:
				return level
			for _ in range(len(q) - ptr):
				top = q[ptr]
				if top == Num2:
					return level
				ptr += 1
				for i in adj[top]:
					if not visited[i]:
						visited[i] = True
						q.append(i)
			level += 1


class Solution:

	def __init__(self):
		self.mxp = 9999
		self.prime = [1 for i in range(10001)]
		self.prime[1] = 0
		for i in range(2, self.mxp + 1):
			if self.prime[i] == 1:
				j = 2
				while j * i <= self.mxp:
					self.prime[j * i] = 0
					j += 1

	def bfs(self, source, destination):
		dp = [-1 for i in range(10001)]
		vis = [0 for i in range(10001)]
		q = []
		q.append(source)
		dp[source] = 0
		vis[source] = 0
		while len(q) > 0:
			current = q.pop(0)
			if vis[current] == 1:
				continue
			vis[current] = 1
			s = str(current)
			for i in range(4):
				for j in range(10):
					ch = chr(j + 48)
					if ch == s[i] or (ch == '0' and i == 0):
						continue
					nxt = s[0:i] + ch + s[i + 1:]
					nxtN = int(nxt)
					if self.prime[nxtN] == 1 and dp[nxtN] == -1:
						dp[nxtN] = 1 + dp[current]
						q.append(nxtN)
		return dp[destination]

	def solve(self, Num1, Num2):
		return self.bfs(Num1, Num2)


class Solution:

	def solve(self, Num1, Num2):
		primes = [True] * 10000
		primes[0] = False
		primes[1] = False
		i = 2
		while i * i < 10000:
			if primes[i]:
				j = 2 * i
				while j < 10000:
					primes[j] = False
					j += i
			i += 1
		q = []
		visited = [False] * 10000
		q.append([Num1, 0])
		visited[Num1] = True
		while q:
			(num, steps) = q.pop(0)
			if num == Num2:
				return steps
			num = str(num)
			for i in range(len(num)):
				temp = list(num)
				start = 1 if i == 0 else 0
				for code in range(start, 10):
					ch = chr(ord('0') + code)
					temp[i] = ch
					new_num = int(''.join(temp))
					if primes[new_num] and (not visited[new_num]):
						visited[new_num] = True
						q.append([new_num, steps + 1])
		return -1


from collections import deque
N = 10001
prime = [1] * N

def sieve():
	prime[0] = 0
	prime[1] = 0
	i = 2
	while i * i < N:
		if prime[i]:
			j = 2
			while i * j < N:
				prime[i * j] = 0
				j += 1
		i += 1
sieve()

class Solution:

	def solve(self, Num1, Num2):
		dp = [-1 for i in range(N)]
		vis = [0 for i in range(N)]
		q = deque()
		q.append(Num1)
		dp[Num1] = 0
		while q:
			nd = q.popleft()
			if vis[nd]:
				continue
			vis[nd] = 1
			num = str(nd)
			for i in range(4):
				for j in range(10):
					dig = chr(ord('0') + j)
					if dig == num[i] or (dig == '0' and i == 0):
						continue
					next = num[0:i] + dig + num[i + 1:]
					next = int(next)
					if prime[next] and dp[next] == -1:
						dp[next] = 1 + dp[nd]
						q.append(next)
		return dp[Num2]


from collections import defaultdict

class Solution:

	def check(self, a, b):
		total = 0
		for (c, d) in zip(a, b):
			if c != d:
				total += 1
		if total > 1:
			return False
		return True
	global primes
	global hsh
	primes = [1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]
	hsh = defaultdict(lambda : False)
	for prime in primes:
		hsh[prime] = True

	def solve(self, Num1, Num2):
		global primes
		global hsh
		N = len(primes)
		visited = [False] * 10000
		parents = [i for i in range(10000)]
		queue = []
		queue.append(Num1)
		visited[Num1] = True
		total = 0
		while len(queue) != 0:
			s = queue.pop(0)
			if s == Num2:
				break
			neighs = []
			for i in range(1, 10):
				pprime = s + 1000 * i
				if hsh[pprime]:
					neighs.append(pprime)
				pprime = s - 1000 * i
				if hsh[pprime]:
					neighs.append(pprime)
			for i in range(1, 10):
				pprime = s + 100 * i
				if hsh[pprime]:
					neighs.append(pprime)
				pprime = s - 100 * i
				if hsh[pprime]:
					neighs.append(pprime)
			for i in range(1, 10):
				pprime = s + 10 * i
				if hsh[pprime]:
					neighs.append(pprime)
				pprime = s - 10 * i
				if hsh[pprime]:
					neighs.append(pprime)
			for i in range(1, 10):
				pprime = s + 1 * i
				if hsh[pprime]:
					neighs.append(pprime)
				pprime = s - 1 * i
				if hsh[pprime]:
					neighs.append(pprime)
			for neigh in neighs:
				if visited[neigh] == False and self.check(str(s), str(neigh)):
					parents[neigh] = s
					queue.append(neigh)
					visited[neigh] = True
		if parents[Num2] == Num2:
			return -1
		current_node = Num2
		while current_node != Num1:
			current_node = parents[current_node]
			total += 1
		return total


import queue

class Graph:

	def __init__(self, V):
		self.V = V
		self.graph = [[] for i in range(V)]

	def addEdge(self, u, v):
		self.graph[u].append(v)
		self.graph[v].append(u)

	def bfs(self, start, end):
		Q = queue.Queue()
		Q.put(start)
		visited = [0] * self.V
		visited[start] += 1
		while not Q.empty():
			node = Q.queue[0]
			Q.get()
			for j in self.graph[node]:
				if not visited[j]:
					if j == end:
						return visited[node]
					visited[j] = visited[node] + 1
					Q.put(j)
		return -1

class Helper:

	def getAllprimes(self):
		primes = [True] * 10000
		i = 2
		while i * i < 10000:
			if primes[i] == True:
				for j in range(i + i, 10000, i):
					primes[j] = False
			i += 1
		self.Primes = []
		for i in range(1000, 10000):
			if primes[i]:
				self.Primes.append(i)
		return

	def isDifByOne(self, one, two):
		count = 0
		for i in range(4):
			if one[i] != two[i]:
				count += 1
		return count == 1

	def makeGraph(self):
		self.getAllprimes()
		V = len(self.Primes)
		self.G = Graph(V)
		for i in range(V):
			for j in range(i + 1, V):
				if self.isDifByOne(str(self.Primes[i]), str(self.Primes[j])):
					self.G.addEdge(i, j)
h = Helper()
h.makeGraph()

class Solution:

	def solve(self, Num1, Num2):
		(n1, n2) = (None, None)
		for i in range(h.G.V):
			if h.Primes[i] == Num1:
				n1 = i
			if h.Primes[i] == Num2:
				n2 = i
		if n1 != None and n2 != None:
			return h.G.bfs(n1, n2)
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(Num1, Num2) = map(int, input().split())
		ob = Solution()
		print(ob.solve(Num1, Num2))


def primeList():
	arr = [0] * 10000
	for i in range(2, 10000):
		if arr[i] == 0:
			for i in range(i + i, 10000, i):
				arr[i] = 1
	return arr

class Solution:

	def solve(self, Num1, Num2):
		n1 = Num1
		n2 = Num2
		prime = primeList()
		vis = [0] * 10000
		queue = [n1]
		ans = 0
		while queue:
			n = len(queue)
			ans += 1
			for i in range(n):
				val = queue.pop(0)
				if vis[val] == 0:
					if val == n2:
						return ans - 1
					vis[val] = 1
					newval = str(val)
					for i in range(4):
						if i == 0:
							for pos in '123456789':
								newval1 = newval[:i] + pos + newval[i + 1:]
								val = int(newval1)
								if vis[val] == 0 and prime[val] == 0:
									queue.append(val)
						else:
							for pos in '0123456789':
								newval1 = newval[:i] + pos + newval[i + 1:]
								val = int(newval1)
								if vis[val] == 0 and prime[val] == 0:
									queue.append(val)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(Num1, Num2) = map(int, input().split())
		ob = Solution()
		print(ob.solve(Num1, Num2))


def SieveOfEratosthenes(n):
	n = 10000
	prime = [1 for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == 1:
			for i in range(p * p, n + 1, p):
				prime[i] = 0
		p += 1
	return prime

def ss(n):
	l = []
	for i in range(1, 10):
		l.append(int(str(i) + str(n)[1:]))
	for i in range(1, 4):
		for j in range(10):
			l.append(int(str(n)[:i] + str(j) + str(n)[i + 1:]))
	return l

class Solution:

	def solve(self, n1, n2):
		l = SieveOfEratosthenes(0)
		if not l[n1] or not l[n2]:
			return -1
		q = [n1]
		l[n1] = 0
		ans = 0
		while q:
			q1 = []
			for n in q:
				if n == n2:
					return ans
				t = ss(n)
				for j in t:
					if l[j]:
						q1.append(j)
						l[j] = 0
			q = q1
			ans += 1
		return ans


class Solution:

	def solve(self, num1, num2):
		from collections import defaultdict, deque
		if num1 == num2:
			return 0

		def sol():
			t = [True for i in range(10000)]
			p = 2
			n = 10000
			while p * p <= n:
				if t[p]:
					for i in range(p * p, n, p):
						t[i] = False
				p += 1
			return t
		pri = sol()

		def ch(v):
			return pri[v]
		s1 = str(num1)
		s2 = str(num2)
		q = deque()
		q.append((s1, 0))
		d = set()
		while q:
			t = q.popleft()
			d.add(t[0])
			for i in range(4):
				for k in range(10):
					cr = t[0]
					if i == 0 and k == 0:
						continue
					if k != int(cr[i]):
						cr = cr[:i] + str(k) + cr[i + 1:]
						if cr not in d and ch(int(cr)):
							if cr == s2:
								return t[1] + 1
							q.append((cr, t[1] + 1))
		return -1


from collections import *

class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]
		self.prime[1] = 0
		for i in range(2, 10000):
			if self.prime[i] == 1:
				j = 2
				while j * i <= 9999:
					self.prime[j * i] = 0
					j += 1

	def bfs(self, source, destination):
		dp = [-1 for i in range(10001)]
		visited = [0 for i in range(10001)]
		queue = deque()
		queue.append(source)
		dp[source] = 0
		while queue:
			current = queue.popleft()
			if visited[current] == 1:
				continue
			s = str(current)
			visited[current] = 1
			for i in range(4):
				for j in range(10):
					c = chr(j + 48)
					if c == s[i] or (c == '0' and i == 0):
						continue
					nxt = s[:i] + c + s[i + 1:]
					nxt = int(nxt)
					if self.prime[nxt] == 1 and dp[nxt] == -1:
						dp[nxt] = 1 + dp[current]
						queue.append(nxt)
					if dp[destination] != -1:
						return dp[destination]
		return dp[destination]

	def solve(self, Num1, Num2):
		return self.bfs(Num1, Num2)


import collections

class Solution:

	def sieve(self):
		n = 9999
		prime = [True] * (n + 1)
		(prime[0], prime[1]) = (False, False)
		i = 2
		while i * i <= n:
			if prime[i]:
				for j in range(i * i, n + 1, i):
					prime[j] = False
			i += 1
		return prime

	def solve(self, num1, num2):
		num1Arr = []
		num2Arr = []
		isPrime = self.sieve()
		for c in str(num1):
			num1Arr.append(c)
		for c in str(num2):
			num2Arr.append(c)
		queue = collections.deque()
		queue.append(num1Arr)
		distance = 0
		visited = set()
		while queue:
			n = len(queue)
			for i in range(n):
				arr = queue.popleft()
				tupleArr = tuple(arr)
				if tupleArr in visited:
					continue
				if arr == num2Arr:
					return distance
				visited.add(tupleArr)
				for i in range(4):
					temp = arr[i]
					for d in '0123456789':
						if i == 0 and d == '0':
							continue
						arr[i] = d
						if tuple(arr) in visited:
							continue
						newNum = int(''.join(arr))
						if isPrime[newNum]:
							newArr = arr[:]
							queue.append(newArr)
					arr[i] = temp
			distance += 1
		return -1


from collections import deque

class Solution:

	def isprime(self, n):
		if n == 2:
			return True
		if n == 3:
			return True
		if n % 2 == 0:
			return False
		if n % 3 == 0:
			return False
		i = 5
		w = 2
		while i * i <= n:
			if n % i == 0:
				return False
			i += w
			w = 6 - w
		return True

	def solve(self, Num1, Num2):
		if not self.isprime(Num1) or not self.isprime(Num2):
			return -1
		if Num1 == Num2:
			return 0
		seen = set()
		q = deque([(Num1, 0)])
		seen.add(Num1)
		while q:
			(front, count) = q.popleft()
			for i in range(10):
				tmp = front // 10
				tmp = tmp * 10 + i
				if tmp == Num2:
					return count + 1
				if tmp not in seen and self.isprime(tmp):
					seen.add(tmp)
					q.append((tmp, count + 1))
			for i in range(10):
				end = front % 10
				tmp = front // 100
				tmp = (tmp * 10 + i) * 10 + end
				if tmp == Num2:
					return count + 1
				if tmp not in seen and self.isprime(tmp):
					seen.add(tmp)
					q.append((tmp, count + 1))
			for i in range(10):
				end = front % 100
				tmp = front // 1000
				tmp = (tmp * 10 + i) * 100 + end
				if tmp == Num2:
					return count + 1
				if tmp not in seen and self.isprime(tmp):
					seen.add(tmp)
					q.append((tmp, count + 1))
			for i in range(1, 10):
				end = front % 1000
				tmp = i * 1000 + end
				if tmp == Num2:
					return count + 1
				if tmp not in seen and self.isprime(tmp):
					seen.add(tmp)
					q.append((tmp, count + 1))
		return -1


import collections

class Solution:

	def integer(self, arr):
		s = ''.join(arr)
		return int(s)

	def sieve(self):
		n = 9999
		primes = [True] * (n + 1)
		primes[0] = False
		primes[1] = False
		i = 2
		while i * i <= n:
			if primes[i]:
				for j in range(i * i, n + 1, i):
					primes[j] = False
			i += 1
		return primes

	def solve(self, num1, num2):
		isPrime = self.sieve()
		num1Arr = []
		num2Arr = []
		for c in str(num1):
			num1Arr.append(c)
		for c in str(num2):
			num2Arr.append(c)
		q = collections.deque()
		q.append((num1Arr, 0))
		visited = set()
		shortestPath = float('inf')
		while q:
			(arr, count) = q.popleft()
			if tuple(arr) in visited:
				continue
			if arr == num2Arr:
				shortestPath = min(shortestPath, count)
			visited.add(tuple(arr))
			for i in range(4):
				temp = arr[i]
				for d in '0123456789':
					if i == 0 and d == '0':
						continue
					arr[i] = d
					if tuple(arr) not in visited:
						num = self.integer(arr)
						if isPrime[num]:
							newArr = arr[:]
							q.append((newArr, count + 1))
				arr[i] = temp
		return shortestPath


import collections
import math

class Solution:

	def isPrime(self):
		primeArr = set()
		for i in range(1000, 9999):
			for factor in range(2, int(math.sqrt(i)) + 1):
				if i % factor == 0:
					break
			else:
				primeArr.add(i)
		return primeArr

	def solve(self, Num1, Num2):
		q = collections.deque()
		primes = self.isPrime()
		num1Arr = []
		num1Str = str(Num1)
		num2Str = str(Num2)
		for c in num1Str:
			num1Arr.append(c)
		q.append((num1Arr, 0))
		visited = set()
		shortestPath = float('inf')
		while q:
			(arr, count) = q.popleft()
			num = ''.join(arr)
			if num == num2Str:
				shortestPath = min(shortestPath, count)
			if num in visited:
				continue
			visited.add(num)
			for i in range(4):
				temp = arr[i]
				for d in '0123456789':
					if i == 0 and d == '0':
						continue
					arr[i] = d
					newNum = ''.join(arr)
					if newNum not in visited:
						newNum = int(newNum)
						if newNum in primes:
							newArr = arr[:]
							q.append((newArr, count + 1))
				arr[i] = temp
		return shortestPath


from collections import deque
import math

class Solution:

	def solve(self, Num1, Num2):
		seive = [True] * 10000

		def seive_fill():
			sqrt = int(math.sqrt(9999))
			for i in range(2, sqrt + 1):
				if seive[i]:
					for j in range(2 * i, 10000, i):
						seive[j] = False
		if Num1 == Num2:
			return 0
		seive_fill()
		visited = set([str(Num1)])
		q = deque([str(Num1)])
		(level, t) = (0, str(Num2))
		while q:
			size = len(q)
			level += 1
			for _ in range(size):
				num = q.popleft()
				for i in range(4):
					for k in range(10):
						if i == 0 and k == 0:
							continue
						key = num[:i] + str(k) + num[i + 1:]
						if key == t:
							return level
						if key not in visited and seive[int(key)]:
							visited.add(key)
							q.append(key)
		return -1


class Solution:

	def Sieve(self):
		primes = set()
		prime = [True] * 10000
		p = 2
		while p * p <= 9999:
			if prime[p]:
				for i in range(p * p, 10000, p):
					prime[i] = False
			p += 1
		for p in range(1000, 10000):
			if prime[p]:
				primes.add(p)
		return primes

	def getNextNumbers(self, num, primes):
		res = []
		for i in range(4):
			temp = str(num)
			for j in range(10):
				val = int(temp[:i] + str(j) + temp[i + 1:])
				if val != num and val > 999 and (val in primes):
					res.append(val)
		return res

	def solve(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		primes = self.Sieve()
		visited = set()
		count = 0
		q = []
		visited.add(Num1)
		q.append((Num1, 0))
		while True:
			pair = q.pop(0)
			val = pair[0]
			count = pair[1]
			if val == Num2:
				return count
			nums = self.getNextNumbers(val, primes)
			for num in nums:
				if num not in visited:
					visited.add(num)
					q.append((num, count + 1))
		return -1


from math import floor, sqrt

class Solution:

	def isPrime(self, num):
		if num % 2 == 0:
			return False
		for i in range(3, floor(sqrt(num)) + 1, 2):
			if num % i == 0:
				return False
		return True

	def getNextNumbers(self, num):
		res = []
		for i in range(4):
			temp = str(num)
			for j in range(10):
				val = int(temp[:i] + str(j) + temp[i + 1:])
				if val != num and val > 999 and self.isPrime(val):
					res.append(val)
		return res

	def solve(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		visited = set()
		count = 0
		q = []
		visited.add(Num1)
		q.append((Num1, 0))
		while True:
			pair = q.pop(0)
			val = pair[0]
			count = pair[1]
			if val == Num2:
				return count
			nums = self.getNextNumbers(val)
			for num in nums:
				if num not in visited:
					visited.add(num)
					q.append((num, count + 1))
		return -1


from math import sqrt

def is_prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def generate_all(x):
	ans = set()
	for i in range(4):
		for j in range(10):
			temp = int(x[:i] + str(j) + x[i + 1:])
			if temp >= 1000 and temp != int(x) and is_prime(temp):
				ans.add(temp)
	return list(ans)
from collections import deque

class Solution:

	def solve(self, Num1, Num2):
		Q = deque()
		Q.append([Num1, 0])
		vis = set()
		while Q:
			temp = Q.popleft()
			if temp[0] == Num2:
				return temp[1]
			for i in generate_all(str(temp[0])):
				if i not in vis:
					Q.append([i, temp[1] + 1])
					vis.add(i)
		return -1