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 one single digit at a time. Every number obtained after changing a digit should be 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 required 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 constructor of the class Solution to precompute a list of prime numbers.  
	Complete function shortestPath() 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(NlogN)
Expected Auxiliary Space: O(N)
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 __init__(self):

        # Every index of prime stores zero or one

        # If prime[i] is zero means i is not a prime

        # If prime[i] is one means i is a prime

        self.prime=[1 for i in range(10001)]



    def shortestPath(self,Num1,Num2):

        # Complete this function using prime list







Solutions:
from collections import deque
from math import sqrt

class Solution:

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

	def convertIntToList(self, int_num):
		num_list = [0 for _ in range(4)]
		i = 3
		while i >= 0:
			num_list[i] = int_num % 10
			int_num //= 10
			i -= 1
		return list(num_list)

	def shortestPath(self, Num1, Num2):

		def dp(curr_num):
			if curr_num == Num2:
				return 0
			queue = deque([(curr_num, 0)])
			seen = {curr_num}
			while queue:
				(num, steps) = queue.popleft()
				num_list = self.convertIntToList(num)
				if num == Num2:
					self.ans = min(self.ans, steps)
				if steps < self.ans:
					for j in range(4):
						temp_num_list = list(num_list)
						for n in range(10):
							if n != num_list[j]:
								temp_num_list[j] = n
								num_list_int = int(''.join((str(x) for x in temp_num_list)))
								if num_list_int not in seen and self.prime[num_list_int] == 1 and (num_list_int >= 1000):
									seen.add(num_list_int)
									queue.append((num_list_int, steps + 1))
			return self.ans
		self.ans = float('inf')
		return dp(Num1)


from math import sqrt, ceil
from collections import defaultdict

class Solution:

	def __init__(self):
		N = 10000
		self.adjs = defaultdict(set)
		self.prime = [1 for i in range(N + 1)]
		self.prime[0] = self.prime[1] = 0
		for i in range(2, ceil(sqrt(N)) + 1):
			if not self.prime[i]:
				continue
			for j in range(i * i, N + 1, i):
				self.prime[j] = 0
		for v in range(1000, N):
			if not self.prime[v]:
				continue
			rs = (v % 1000, v // 1000 * 1000 + v % 100, v // 100 * 100 + v % 10, v // 10 * 10)
			for d in range(10):
				for nv in [d * m + r for (r, m) in zip(rs, (1000, 100, 10, 1))]:
					if nv != v and nv > 1000 and self.prime[nv]:
						self.adjs[v].add(nv)

	def shortestPath(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		g = [10 ** 6] * 10000
		g[Num1] = 0
		(q1, q2) = ([], [Num1])
		dist = 1
		while q2:
			(q1, q2) = (q2, q1)
			q2.clear()
			while q1:
				v = q1.pop()
				for nv in self.adjs[v]:
					if dist < g[nv]:
						if nv == Num2:
							return dist
						g[nv] = dist
						q2.append(nv)
			dist += 1
		return -1


from collections import deque, defaultdict

def primes(arr, n):
	arr = [True for i in range(n)]
	(arr[0], arr[1]) = (False, False)
	for i in range(2, int(n ** 0.5) + 1):
		if arr[i]:
			for j in range(i * i, n, i):
				arr[j] = False
	return arr

def solve(num1, num2, visited, isprime):
	q = deque([(num1, 0)])
	visited[num1] = True
	while q:
		(node, dist) = q.popleft()
		if node == num2:
			return dist
		node = list(str(node))
		for ind in range(0, 4):
			for digit in range(0, 10):
				if (ind == 0 and digit != 0 or ind != 0) and node[ind] != str(digit):
					actual_digit = node[ind]
					node[ind] = str(digit)
					neigh = int(''.join(node))
					if isprime[neigh] and (not visited[neigh]):
						visited[neigh] = True
						q.append((neigh, dist + 1))
					node[ind] = actual_digit
	return 0

class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]
		self.prime = primes(self.prime, 10001)

	def shortestPath(self, num1, num2):
		visited = defaultdict(lambda : False)
		distance = solve(num1, num2, visited, self.prime)
		return distance


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 shortestPath(self, Num1, Num2):
		return self.bfs(Num1, Num2)


import math
import itertools
from collections import deque
MAX_N = 9999

class MITM_Side:

	def __init__(self, n):
		self.visited = set([n])
		self.frontline = deque([n])

class Solution:

	def _mark_multiples_as_not_prime(self, n):
		for i in range(n * n, MAX_N + 1, n):
			self.prime[i] = False

	def __init__(self):
		self.prime = [True for i in range(MAX_N + 1)]
		self.prime[0] = self.prime[1] = False
		for i in range(2, int(math.sqrt(MAX_N))):
			if self.prime[i]:
				self._mark_multiples_as_not_prime(i)

	def _generate_all_neighbors_on_position(self, n, position):
		position_coefficient = 10 ** position
		digit_at_position = n // position_coefficient % 10
		n_template = n - digit_at_position * position_coefficient
		start = 1 if position == 3 else 0
		neighbor_primes = []
		for i in range(start, 10):
			nn = n_template + i * position_coefficient
			if self.prime[nn] and nn != n:
				neighbor_primes.append(nn)
		return neighbor_primes

	def get_all_prime_neighbors(self, n):
		return list(itertools.chain(self._generate_all_neighbors_on_position(n, 3), self._generate_all_neighbors_on_position(n, 2), self._generate_all_neighbors_on_position(n, 1), self._generate_all_neighbors_on_position(n, 0)))

	def shortestPath(self, Num1, Num2):
		side1 = MITM_Side(Num1)
		side2 = MITM_Side(Num2)
		rounds_count = 0
		if Num1 == Num2:
			return rounds_count
		while rounds_count < len(self.prime):
			rounds_count += 1
			(side1, side2) = (side2, side1)
			new_frontline = deque()
			for n in side1.frontline:
				for prime_neighbor in self.get_all_prime_neighbors(n):
					if prime_neighbor in side2.visited:
						return rounds_count
					if prime_neighbor not in side1.visited:
						new_frontline.append(prime_neighbor)
						side1.visited.add(prime_neighbor)
			side1.frontline = new_frontline


from collections import deque

class Solution:

	def __init__(self):
		self.digit = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
		self.prime = [1 for i in range(10001)]
		self.prime[0] = 0
		self.prime[1] = 0
		for i in range(2, 10001):
			if self.prime[i]:
				for j in range(2, 10001):
					if j * i >= 10001:
						break
					else:
						self.prime[i * j] = 0

	def findPath(self, src, dst):
		answer = [-1] * 10001
		visite = [False] * 10001
		q = deque()
		q.append(str(src))
		answer[src] = 0
		visite[src] = False
		while len(q) != 0:
			current = q.popleft()
			if visite[int(current)]:
				continue
			visite[int(current)] = True
			for i in range(len(current)):
				for num in self.digit:
					if current[i] == num or (num == '0' and i == 0):
						continue
					else:
						next = list(current)
						next[i] = num
						next = ''.join(next)
						if self.prime[int(next)] == True and answer[int(next)] == -1:
							q.append(next)
							answer[int(next)] = answer[int(current)] + 1
		return answer[dst]

	def shortestPath(self, Num1, Num2):
		return self.findPath(Num1, Num2)


class Solution:

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

	def shortestPath(self, num1, num2):
		vis = [0 for _ in range(10001)]
		q = [[num1, 0]]
		vis[num1] = 1
		while q:
			(currnum, currlvl) = q.pop(0)
			if currnum == num2:
				return currlvl
			for i in range(4):
				snum = str(currnum)
				for dig in range(10):
					if snum[i] == str(dig) or (i == 0 and dig == 0):
						continue
					newsnum = snum[:i] + str(dig) + snum[i + 1:]
					newnum = int(newsnum)
					if self.prime[newnum] and (not vis[newnum]):
						q.append([newnum, currlvl + 1])
						vis[newnum] = 1
		return -1


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

class Solution:

	def __init__(self):
		for i in range(2, N):
			if not prime[i]:
				continue
			for j in range(2 * i, N, i):
				prime[j] = 0

	def shortestPath(self, num1, num2):
		if num1 == num2:
			return 0
		dq = deque()
		dq.extend([num1])
		dis = [-1] * N
		dis[num1] = 0
		while len(dq):
			u = dq.popleft()
			for digpos in range(3, -1, -1):
				for dig in range(10):
					num = list(str(u))
					if digpos == 0 and dig == 0:
						continue
					num[digpos] = chr(ord('0') + dig)
					num = int(''.join(num))
					if prime[num] and dis[num] == -1:
						dis[num] = dis[u] + 1
						dq.append(num)
						if num == num2:
							return dis[num]
		return -1


from math import ceil, sqrt
from collections import deque

class Prime:
	primes = None

	def __init__(self):
		if Prime.primes:
			return
		self.sieve()

	def sieve(self, N=10000):
		Prime.primes = [True] * N
		for num in range(2, round(ceil(sqrt(N))) + 1):
			if not Prime.primes[num]:
				continue
			for i in range(num * num, N, num):
				Prime.primes[i] = False

	def checkPrime(self, num):
		return self.primes[num]

class Solution:

	def __init__(self):
		self.prime = Prime()

	def shortestPath(self, base, target):
		base = str(base)
		target = str(target)
		queue = deque()
		seen = set()
		queue.append((base, 0))
		seen.add(base)
		while queue:
			(num, moves) = queue.popleft()
			if num == target:
				return moves
			for i in range(4):
				for j in range(10):
					newNum = num[:i] + str(j) + num[i + 1:]
					if newNum == num:
						continue
					if int(newNum) < 1000:
						continue
					if newNum in seen:
						continue
					if self.prime.checkPrime(int(newNum)):
						queue.append((newNum, 1 + moves))
						seen.add(newNum)
		return -1


class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10000)]
		self.prime[0] = 0
		self.prime[1] = 0
		for i in range(10000):
			if self.prime[i] == 0:
				continue
			for j in range(i * i, 10000, i):
				self.prime[j] = 0
		self.prime = {i for (i, e) in enumerate(self.prime) if e == 1 and i >= 1000}

	def shortestPath(self, Num1, Num2):

		def nbrs(n, st):
			for i in range(1, 5):
				m = 10 ** i
				l = n % m
				h = n // m * m
				r = l % 10 ** (i - 1)
				for j in range(10):
					x = h + j * 10 ** (i - 1) + r
					if x != n and x >= 1000 and (x in st):
						yield x
		steps = 0
		q = [Num1]
		visited = {Num1}
		while q:
			nq = []
			for e in q:
				if e == Num2:
					return steps
				for nbr in nbrs(e, self.prime):
					if nbr not in visited:
						visited.add(nbr)
						nq.append(nbr)
				q = nq
			steps += 1
		return steps


class Solution:

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

	def shortestPath(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		if Num2 < Num1:
			(Num2, Num1) = (Num1, Num2)
		visited = set([])
		q = [(Num1, 1)]
		while q:
			(tmp, count) = q.pop(0)
			s = str(tmp)
			for i in range(4):
				for j in range(10):
					t = str(j)
					if s[i] == t or (i == 0 and j == 0):
						continue
					newN = int(s[:i] + t + s[i + 1:])
					if newN == Num2:
						return count
					if newN not in visited and self.prime[newN]:
						q.append((newN, count + 1))
						visited.add(newN)
		return -1


import heapq

class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]

	def shortestPath(self, Num1, Num2):
		self.prime[0] = 0
		self.prime[1] = 0
		for i in range(2, 10001):
			if self.prime[i]:
				for j in range(i * i, 10001, i):
					self.prime[j] = 0
		if Num1 == Num2:
			return 0
		q = [Num1]
		dis = [-1 for i in range(10001)]
		dis[Num1] = 0
		pow10 = [1, 10, 100, 1000]
		digits = [0, 0, 0, 0]
		pre = [-1 for i in range(10001)]
		while q:
			n = q.pop(0)
			x = n
			cnt = 0
			while x > 0:
				digits[cnt] = x % 10
				x = x // 10
				cnt += 1
			for i in range(4):
				for j in range(10):
					if i == 3 and j == 0:
						continue
					new_n = n + pow10[i] * (j - digits[i])
					if self.prime[new_n] and dis[new_n] == -1:
						dis[new_n] = dis[n] + 1
						q.append(new_n)
						pre[new_n] = n
						if new_n == Num2:
							x = new_n
							s = []
							while pre[x] != -1:
								s.append(pre[x])
								x = pre[x]
							return dis[new_n]
		return -1


class Solution:

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

	def shortestPath(self, Num1, Num2):
		from collections import deque
		(Num1, Num2) = (min(Num1, Num2), max(Num1, Num2))
		if Num1 == Num2:
			return 0
		vis = [False] * 10 ** 4
		deq = deque([Num1])
		step = 0
		while deq:
			for i in range(len(deq)):
				x = deq.popleft()
				for pos in range(4):
					for digit in range(10):
						if pos == 0 and digit == 0:
							continue
						s = str(x)
						s = s[:pos] + str(digit) + s[pos + 1:]
						if int(s) == Num2:
							return step + 1
						if not vis[int(s)] and self.prime[int(s)]:
							vis[int(s)] = True
							deq.append(int(s))
			step += 1
		return -1


import math

class Solution:

	def __init__(self):
		self.prime = [0 for i in range(10001)]

	def shortestPath(self, Num1, Num2):
		self.prime = [0 for i in range(10001)]
		for i in range(2, 10001):
			if self.prime[i] == 0:
				for j in range(i + i, 10001, i):
					self.prime[j] = 1
		q = [Num1]
		steps = 0
		while q:
			q.append(-1)
			while q[0] != -1:
				t = q.pop(0)
				if t == Num2:
					return steps
				for j in range(4):
					start = 0 if j != 3 else 1
					p = int(math.pow(10, j))
					n = t
					existing = t // p if p != 0 else t
					existing = int(existing % 10)
					n -= p * existing
					for i in range(start, 10):
						if existing != i:
							n += p * i
							if self.prime[n] == 0:
								q.append(n)
								self.prime[n] = 1
							n -= p * i
			q.pop(0)
			steps += 1
		return steps


from collections import defaultdict, deque

class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]
		self.graph = defaultdict(list)
		self.primes = []
		self._generate_prime()
		self._make_graph()

	def shortestPath(self, Num1, Num2):
		q = deque()
		q.append(Num1)
		dist = [float('inf')] * 10001
		dist[Num1] = 0
		visited = [False] * 10001
		while q:
			node = q.popleft()
			if visited[node]:
				continue
			visited[node] = True
			for n in self.graph[node]:
				q.append(n)
				d = dist[node] + 1
				if d < dist[n]:
					dist[n] = d
		if dist[Num2] == float('inf'):
			dist[Num2] = -1
		return dist[Num2]

	def _generate_prime(self):
		self.prime[0] = 0
		self.prime[1] = 0
		for i in range(2, int(10000 ** 0.5) + 1):
			if self.prime[i] == 0:
				continue
			for j in range(i * i, 10001, i):
				self.prime[j] = 0
		for i in range(1000, 10001):
			if self.prime[i] == 0:
				continue
			self.primes.append(i)

	def _make_graph(self):
		for i in range(len(self.primes) - 1):
			a = self.primes[i]
			for j in range(i + 1, len(self.primes)):
				b = self.primes[j]
				if Solution._check(a, b) != 1:
					continue
				self.graph[a].append(b)
				self.graph[b].append(a)

	@staticmethod
	def _check(m, n):
		diff = 0
		(m, n) = (str(m), str(n))
		for i in range(4):
			if m[i] == n[i]:
				continue
			diff += 1
		return diff


class Solution:

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

	def shortestPath(self, Num1, Num2):
		dp = [-1 for i in range(10001)]
		dp[Num1] = 0
		frontier = [str(Num1)]
		while frontier:
			next_frontier = []
			for current in frontier:
				for i in range(4):
					for j in range(10):
						nxt = current[:i] + str(j) + current[i + 1:]
						if int(nxt) > 999 and nxt != current and self.prime[int(nxt)] and (dp[int(nxt)] < 0):
							dp[int(nxt)] = 1 + dp[int(current)]
							if int(nxt) == Num2:
								return dp[int(nxt)]
							next_frontier.append(nxt)
			frontier = next_frontier
		return dp[Num2]


from collections import defaultdict

class Solution:

	def __init__(self):
		self.prime = [True for i in range(10001)]
		l = len(self.prime)
		for i in range(2, l):
			if self.prime[i]:
				for j in range(2, l):
					k = i * j
					if k < l:
						self.prime[k] = False
					else:
						break

	def shortestPath(self, num1, num2):
		graph = defaultdict(list)

		def getDigits(num):
			digits = [0] * 4
			for i in range(4):
				digits[3 - i] = num % 10
				num //= 10
			return digits

		def updateGraph(num):
			digits = getDigits(num)
			for i in range(4):
				mid = num - digits[i] * 10 ** (3 - i)
				for j in range(digits[i] + 1, 10):
					tmp = mid + j * 10 ** (3 - i)
					if self.prime[tmp]:
						graph[num].append(tmp)
						graph[tmp].append(num)
		for i in range(1000, 10000):
			if self.prime[i]:
				updateGraph(i)
		visited = set()
		arr = [num1]
		ans = 0
		while num2 not in arr:
			arr2 = []
			for x in arr:
				if x not in visited:
					arr2.extend(graph[x])
				visited.add(x)
			arr = arr2
			ans += 1
		return ans


from collections import deque

class Solution:

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

	def shortestPath(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		ans = 0
		set1 = set()
		set1.add(Num1)
		set2 = set()
		set2.add(Num2)
		visited = set()
		allDigits = [str(i) for i in range(10)]
		while len(set1) > 0 and len(set2) > 0:
			if len(set1) > len(set2):
				(set1, set2) = (set2, set1)
			newSet = set()
			for front in set1:
				digits = str(front)
				for digit in range(4):
					for i in allDigits:
						if i == digits[digit] or (digit == 0 and i == '0'):
							continue
						nextStr = [digits[j] if j is not digit else i for j in range(4)]
						next = int(''.join(nextStr))
						if next in set2:
							return ans + 1
						if next in visited or self.prime[next] == 0:
							continue
						newSet.add(next)
						visited.add(next)
			set1 = newSet
			ans += 1
		return -1


from collections import defaultdict

class Solution:

	def __init__(self):
		from math import ceil, sqrt
		self.prime = [1 for i in range(10001)]
		self.prime[0] = self.prime[1] = 0
		self.adj = defaultdict(set)
		for i in range(2, ceil(sqrt(10000)) + 1):
			if not self.prime[i]:
				continue
			for j in range(i * i, 10001, i):
				self.prime[j] = 0
		for v in range(1000, 10000):
			if not self.prime[v]:
				continue
			nums = (v % 1000, v // 1000 * 1000 + v % 100, v // 100 * 100 + v % 10, v // 10 * 10)
			for d in range(10):
				for nv in [d * m + r for (r, m) in zip(nums, (1000, 100, 10, 1))]:
					if nv != v and nv > 1000 and self.prime[nv]:
						self.adj[v].add(nv)

	def shortestPath(self, Num1, Num2):
		if Num1 == Num2:
			return 0
		dq1 = []
		dis = [10 ** 4] * 10001
		dis[Num1] = 0
		dq2 = [Num1]
		dist = 1
		while dq2:
			(dq2, dq1) = (dq1, dq2)
			dq2.clear()
			while dq1:
				num = dq1.pop()
				for nm in self.adj[num]:
					if nm == Num2:
						return dist
					if dist < dis[nm]:
						dis[nm] = dist
						dq2.append(nm)
			dist += 1
		return -1


from queue import PriorityQueue

class Solution:

	def __init__(self):
		self.prime = [0] * 10101
		ind = 2
		while ind < 10001:
			if self.prime[ind] == 0:
				i = ind + ind
				while i < 10001:
					self.prime[i] = 1
					i += ind
			ind += 1

	def shortestPath(self, num1, num2):
		if num1 > num2:
			return self.shortestPath(num2, num1)
		que = PriorityQueue()
		que.put((0, num1))
		mp = {}
		mp[num1] = 1
		while que.qsize() > 0:
			n = que.qsize()
			while n > 0:
				(lvl, temp) = que.get()
				if temp == num2:
					return lvl
				lvl = lvl + 1
				for i in [1000, 100, 10, 1]:
					dig = temp // i % 10
					for j in range(1 if i == 1000 else 0, 10):
						form = temp + (j - dig) * i
						if form < 10000 and self.prime[form] == 0 and (form not in mp.keys()) and (form != temp):
							que.put((lvl, form))
							mp[form] = 1
				n -= 1
		return -1


import collections

class Solution:

	def __init__(self):
		self.nmin = 1000
		self.nmax = 9999
		svsize = self.nmax + 1
		sv = self._prime = bytearray((i & 1 for i in range(svsize)))
		sv[1] = 0
		sv[2] = 1
		p = 3
		while p * p <= svsize:
			if sv[p]:
				for j in range(p * p, svsize, p + p):
					sv[j] = 0
			p += 2

	def neighbors(self, num):
		d = 1
		while d < self.nmax:
			cd = num // d % 10
			for nd in range(10):
				nb = num + d * (nd - cd)
				if nb != num and self._prime[nb] and (nb >= self.nmin):
					yield nb
			d *= 10

	def shortestPath(self, Num1, Num2):
		seen = {}
		bfs = collections.deque()
		bfs.append((Num1, 0))
		while bfs:
			(num, plen) = bfs.popleft()
			if num == Num2:
				return plen
			if num in seen:
				continue
			seen[num] = plen
			for nnum in self.neighbors(num):
				bfs.append((nnum, plen + 1))
		return -1


class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]
		self.graph = {}

	def set_prime(self):
		i = 2
		while i * i <= len(self.prime):
			j = i + i
			while j < len(self.prime):
				self.prime[j] = 0
				j += i
			i += 1

	def get_adj(self, num):
		adj = []
		pow = 10
		if num in self.graph:
			return self.graph[num]
		for i in range(4):
			for j in range(0, 10):
				if i == 3 and j == 0:
					continue
				rem = num % pow
				n = num - rem + j * (pow // 10)
				if i != 0:
					n += rem % (pow // 10)
				if self.prime[n] and n != num:
					adj.append(n)
			pow *= 10
		self.graph[num] = adj
		return adj

	def shortestPath(self, Num1, Num2):
		self.set_prime()
		if Num1 == Num2:
			return 0
		queue = [Num1]
		traveled = {Num1: 0}
		while queue != []:
			ele = queue.pop(0)
			adj = self.get_adj(ele)
			for i in adj:
				if i == Num2:
					return traveled[ele] + 1
				if i not in traveled:
					traveled[i] = traveled[ele] + 1
					queue.append(i)
		return -1


class Solution:

	def __init__(self):
		self.prime = [1 for i in range(10001)]
		self.prime[0] = 0
		self.prime[1] = 0
		for i in range(10000):
			if self.prime[i] == 0:
				continue
			for j in range(i * i, 10000, i):
				self.prime[j] = 0
		self.prime = {i for (i, e) in enumerate(self.prime) if e == 1 and i >= 1000}

	def shortestPath(self, Num1, Num2):

		def func(n, st):
			for i in range(1, 5):
				m = 10 ** i
				l = n % m
				h = n // m * m
				r = l % 10 ** (i - 1)
				for k in range(10):
					x = h + k * 10 ** (i - 1) + r
					if x != n and x >= 1000 and (x in st):
						yield x
		ans = 0
		res = [Num1]
		done_already = {Num1}
		while res:
			dibba = []
			for e in res:
				if e == Num2:
					return ans
				for i in func(e, self.prime):
					if i not in done_already:
						done_already.add(i)
						dibba.append(i)
				res = dibba
			ans += 1
		return ans