PPATH - Prime Path

背景 首相们对安全局长带来的消息感到非常不安，他们说他们将为了安全考虑改变首相房间门牌号上面的门牌号码。 ——要不时地改变门牌号，这样可以使敌人处于迷惑之中。 ——但是，我现在的门牌号是1033号，它是一个质数，我有质数强迫症。我不能忍受我的门牌号不是质数。 ——我知道，所以你的新门牌号8179号也是一个质数。你只需在你办公室的门上更换掉原来的四个数字就可以。 ——不，不是那么简单。假设我把第一个数字先改为8，那么在你更改下一个数字之前他将是8033，它不是素数！ ——我明白了，首相，即使在几秒钟内，你也不能忍受一个非质数。 ——是的！因此，你必须提出一种从1033改为8179而且中间全是质数的方案，每次只可以改变其中一个数位上的数字。 例如： 1033 1733 3733 3739 3779 8779 8179 此时，我们一共更改了6次数字，已知更改一次数字需要花费1英镑，因此我们需要花费6英镑。 题目描述 你的任务就是写一个程序，对于任意的起始和终止数字，都求出最小花费。 输入 输入数据有多组，首先是一个数字n，代表之后有n组数据。 其次，在每一组输入中，都包含两个数字m和n，m代表原来的门牌号，n代表现在的门牌号。 其中，m和n都是四位数，而且不含前导0。 输出 每组输入输出一行，输出在此情况下的最小花费。若不存在从m到n的路径，则输出单词“Impossible”。 样例输入 >3 >1033 8179 >1373 8017 >1033 1033 样例输出 >6 >7 >0

 The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now and then, to keep the enemy in the dark. — But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! — I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. — No, it's not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! — I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. — Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime. Now, the minister of finance, who had been eavesdropping, intervened. — No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. — Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? — In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! 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.

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 primes (without leading zeros).

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

3
1033 8179
1373 8017
1033 1033

6
7
0