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