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.

见题面

见题面