质数大臣

大臣们对保安局长的消息感到非常不安，因此他们不得不改变办公室的四位数房间号码。

- 时不时地改变房间号，是一个重要的安全问题。这能使得敌人无从下手。
- 但是你也知道，我选择了1033号码是有原因的。我是Prime minister（注：意译：总理，直译：质数大臣 其实是个冷笑话），你知道！
- 我知道所以你的新号码8179也是一个质数。你只需要在你办公室的门上粘贴四个新的数字。
- 不，不是那么简单。当我把第一个数字改成了8时，那么这个数字就会变成8033，这不是一个质数！
- 我知道，作为Prime minister，你无法忍受在你家门口有一个非质数，甚至几秒钟。
- 对！所以我必须发明一个从1033到8179的质数路径，从一个质数到下一个质数，每次只有一位数字能发生变化。
现在，在一旁偷听的财政部长介入了。
- 请节省没有不必要的开支！我碰巧知道改变一个数字的价格是一磅。
- 嗯，在这种情况下，我需要一个计算机程序来降低成本。你是否知道一些非常便宜的编程大师？
- 实际我已经在做了。你看，有这个编程比赛正在进行...帮助Prime minister找到任何两个给定的四位数的质数之间最便宜的质数路径！当然，第一位数字必须是非零。在上面的情况下，这里有一个解决方案。

1033
1733
3733
3739
3779
8779
8179

这个解决方案的成本是6磅。 请注意，步骤2中粘贴的数字1在最后一步不能重复使用 - 必须购买新的1。

第一行有一个正整数，代表测试数据的数量

对于接下来每一个测试数据，每行有两个数字,且两个数字都是四位质数（没有前导零）。

对于每个测试数据输出一个整数，代表最小的花费，或者输出Impossible

3
1033 8179
1373 8017
1033 1033

6
7
0