Problem Setter: Efat Sikder

Member, IUBAT IITS Programming Wing

Amidst a swirl of security concerns, the Prime Minister received an unsettling directive from the Chief of Security - a mandate to revamp all four-digit room numbers within the cabinet offices. The Prime Minister, understandably attached to his carefully chosen number 1033, expressed his reservations.

"Prime Minister," the Chief of Security explained, "these changes are crucial for maintaining secrecy. Your new number, 8179, is also prime, ensuring the utmost discretion."

"But what if, in the process of altering the digits, we encounter a non-prime number? My door cannot bear such an indignity, even for a fleeting moment," the Prime Minister retorted.

Recognizing the Prime Minister's unwavering commitment to prime numbers, the Minister of Finance intervened. "Prime Minister, let's minimize the expense. Each digit change incurs a cost of one pound. A cost-efficient solution is imperative."

Thus, a quest for the most economical prime path between 1033 and 8179 commenced. The Prime Minister sought the expertise of software gurus to devise an optimal solution, ensuring both security and financial prudence.

Help the prime minister to find the cheapest prime path between any two given four-digit number! The first digit must be nonzero, of course. Here is a solution in the case above.

•     1033
•     1733     
•     3733     
•     3739     
•     3779
•     8779
•     8179     

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input Format

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit and first one is a prime number (without leading zeros).

Output Format

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Samples