PPATH - Prime Path Problem
You are given two prime numbers n and m of 4 digits each, you need to convert n into m in the minimum number of steps, in each step you can change one of the digits of the number n such that a resulting number is also a prime number. Finally, give the number of minimum steps that you would take to complete the task if you can't change n to m then print "Impossible".
Problem Description: Given problem wants you to convert a number N1 to N2 keeping in mind that in each step the number you obtain should also be a prime number and if you are not able to change then you simply print ("Impossible") otherwise Print the minimum number of steps that you took to complete the conversion.
Input: The first line of the input consists of a T number of test cases, each test case contains two numbers n and m.
Output: In each new line print the minimum number of steps that you would take to complete the task.
Example:
Input:
T = 1
N = 1033, M = 8179
Output:
6
Explanation:
The conversion is done in the following way:
1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779- > 8179.
Input:
T = 1
N = 11, M = 23
Output:
2
Explanation:
The conversion is done in the following way:
11 -> 13 -> 23.
The given problem can be solved with the help of a graph. We will follow the steps as:
Program to illustrate Prime path
Output: