Prime Path

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.

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.

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