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:
class Solution:

	def IsPrime(self, num):
		i = 2
		while i * i < num:
			if num % i == 0:
				return False
			i = i + 1
		if i * i == num:
			return False
		return True

	def solve(self, Num1, Num2):
		FourDigitPrimes = {}
		for number in range(1000, 10000):
			if self.IsPrime(number):
				FourDigitPrimes[number] = 0
		from collections import deque
		Queue = deque()
		Queue.append([Num1, 0])
		FourDigitPrimes[Num1] = 1
		while len(Queue) != 0:
			top = Queue.popleft()
			(num, step) = (str(top[0]), top[1])
			if int(num) == Num2:
				return step
			for place in range(0, len(num)):
				temp = num[place]
				for digit in range(0, 10):
					num = num[:place] + str(digit) + num[place + 1:]
					if int(num) in FourDigitPrimes and FourDigitPrimes[int(num)] == 0:
						FourDigitPrimes[int(num)] = 1
						Queue.append([int(num), step + 1])
				num = num[:place] + str(temp) + num[place + 1:]
		return step


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)


from collections import deque
import math

class Solution:

	def __init__(self) -> None:
		self.min_num = 1000
		self.max_num = 9999
		self.sqrt_n = math.ceil(math.sqrt(self.max_num))
		self.digits_0 = '123456789'
		self.digits = '0123456789'

	def checkPrime(self, num):
		for i in range(2, self.sqrt_n):
			if num % i == 0:
				return False
		return True

	def solve(self, num1, num2):
		visited = {}
		queue = deque()
		visited[num1] = 1
		queue.append([num1, 0])
		while len(queue):
			(num, step_count) = queue.popleft()
			if num == num2:
				return step_count
			num = str(num)
			num = [c for c in num]
			for (i, c) in enumerate(num):
				if i == 0:
					for digit in self.digits_0:
						num[i] = digit
						new_num = int(''.join(num))
						num[i] = c
						if self.checkPrime(new_num) and (not visited.get(new_num, 0)):
							visited[new_num] = 1
							queue.append([new_num, step_count + 1])
				else:
					for digit in self.digits:
						num[i] = digit
						new_num = int(''.join(num))
						num[i] = c
						if self.checkPrime(new_num) and (not visited.get(new_num, 0)):
							visited[new_num] = 1
							queue.append([new_num, step_count + 1])
		return -1


class Solution:

	def solve(self, n1, n2):
		v = [1 for _ in range(10000)]
		p = 2
		n = 10000
		while p * p <= n:
			if v[p] == 1:
				for i in range(p * p, n, p):
					v[i] = 0
			p += 1
		ans = 0
		v[n1] = 0

		def ss(x):
			s = str(x)
			t = []
			for i in range(4):
				for new in range(10):
					y = s[:i] + str(new) + s[i + 1:]
					if y[0] != '0' and y != s and (v[int(y)] == 1):
						v[int(y)] = 0
						t.append(int(y))
			return t
		ans = 0
		q = [n1]
		while q:
			q1 = []
			for val in q:
				new = ss(val)
				for child in new:
					if child == n2:
						return ans + 1
					q1.append(child)
			q = q1
			ans += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(Num1, Num2) = map(int, input().split())
		ob = Solution()
		print(ob.solve(Num1, Num2))


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


data = {}

class Solution:

	def getPrimes(self):
		global data
		if 'primes' in data:
			return data['primes']
		n = 10000
		isPrime = [True] * n
		isPrime[0] = isPrime[0] = False
		i = 2
		while i * i < n:
			if isPrime[i]:
				for j in range(i * i, n, i):
					isPrime[j] = False
			i += 1
		data['primes'] = [i for i in range(1000, 10000) if isPrime[i]]
		return data['primes']

	def getGraph(self, primes):
		global data
		if 'graph' in data:
			return data['graph']
		graph = {}
		for i in range(len(primes)):
			if not primes[i] in graph:
				graph[primes[i]] = []
			for j in range(len(primes)):
				if i == j:
					continue
				if self.related(primes[i], primes[j]):
					graph[primes[i]].append(primes[j])
		data['graph'] = graph
		return data['graph']

	def related(self, num1, num2):
		num1 = str(num1)
		num2 = str(num2)
		diff = 0
		for i in range(4):
			if num1[i] != num2[i]:
				diff += 1
		return diff == 1

	def bfs(self, graph, start, end):
		queue = [(start, 0)]
		visited = set()
		visited.add(start)
		while queue:
			(node, step) = queue.pop(0)
			if node == end:
				return step
			step += 1
			for prime in graph[node]:
				if prime not in visited:
					queue.append((prime, step))
					visited.add(prime)
		return -1

	def solve(self, Num1, Num2):
		primes = self.getPrimes()
		graph = self.getGraph(primes)
		return self.bfs(graph, Num1, Num2)


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