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.
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