#P2154. Thekeyof《threebody》

Thekeyof《threebody》

hrw最近在看科幻小说《三体》,被小说里面深厚的历史渊源和宏伟壮阔的奇思构想深深的吸引住了
其中有一个章节讲到截取“审判号”巨型游轮上的残留的三体密码,然而想要得到密码,必须破解一些
相应的关卡,只见密码室的门口写着:
give you two prime number n,m(1000<n,m<9999),find the short path let n change to m,and notice that in the every step,the change number must also be a prime and every step you can only change one digit Here is a solution in the case above. 
n=1009,m=1033
1009 
1039
1033
The step of this solution is 2  Note that the first step we can ignore
if you can solve this problem ,the key of the《threebody》you will get !

Input

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

Output

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

Sample Input

3
1009 1033
1033 1129
1033 1033

Sample Output

2
4
0

HINT

Source