Prime Path

Interview

Time limit2sMemory limit256 MB

Summary

Find the minimum number of single-digit changes to transform one four-digit prime into another, keeping every intermediate number a four-digit prime, using BFS on the graph of primes.

Level: Medium5 of 10
Topics: BFS, Graph, Math
Solved: No attempts yet

Problem

Changyoung likes prime numbers so much that he chose a four-digit prime as his game password. Now he wants to change it to another four-digit prime.

The game allows changing exactly one digit at a time. After every change, the password must still be a four-digit prime. A value below 1000, such as a number whose first digit becomes 0, is not allowed because it is not a four-digit number.

Given two four-digit primes A and B, find the minimum number of digit changes needed to transform A into B. One valid sequence is 1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179, where every intermediate value is also a four-digit prime.

Input

The first line contains the number of test cases T. Each of the next T lines contains two four-digit primes A and B separated by a space.

Output

For each test case, print the minimum number of digit changes needed to transform A into B. If the transformation is impossible, print Impossible.

Examples1

Example 1
Input
```
3
1033 8179
1373 8017
1033 1033
```
Expected output
```
6
7
0
```