# 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:

isprime(x)which takes input as some variable x and return true if it is prime number otherwise false. We will store all the prime numbers in a vector and design a graph with them.isvalid(a,b)function that would return true and false if the combination is valid or not.distof a node from parent node n to other connected nodes in adistarray with -1, and then we call bfs on n if the dist of node m in the graph remains -1 it means it has not been visited during bfs traversal, and we would print "Impossible".Program to illustrate Prime path

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: