You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

内阁部长们对安全局局长的信息感到非常不满，该消息说他们都必须更改办公室的四位数房间号。 ——时不时地改变这些事情，把敌人蒙在鼓里，是一个安全问题。

• 但是看，我选择我的号码1033是有充分理由的。我是总理，你知道的！ ——我知道，因此你的新号码8179也是一个素数。您只需要在办公室门上的四个旧数字上粘贴四个新数字即可。
• 不，没那么简单。假设我将第一个数字更改为8，则数字将读取8033，这不是素数！ ——我明白了，作为总理，你不能忍受门上有一个非素数，哪怕只有几秒钟。
• 正确！因此，我必须发明一个方案，通过素数路径从1033到8179，其中只有一个数字从一个素数更改为下一个素数。 现在，一直在窃听的财政部长进行了干预。
• 请不要不必要的开支！我碰巧知道一个数字的价格是一英镑。
• 嗯，在这种情况下，我需要一个计算机程序来最小化成本。你不认识一些非常便宜的软件大师，对吧？ ——事实上，我是这样做的。你看，有这个编程比赛正在进行中...帮助总理在任何两个给定的四位数素数之间找到最便宜的素数路径！当然，第一个数字必须是非零的。这是上述情况下的解决方案。 1033 1733 3733 3739 3779 8779 8179 该解决方案的成本为6英镑。请注意，在步骤 2 中粘贴的数字 1 不能在最后一步中重复使用 - 必须购买新的 1。

输入格式

一行正数：测试用例数（最多 100 个）。然后，对于每个测试用例，一行，两个数字由空白分隔。这两个数字都是四位数的素数（没有前导零）。

输出格式

每种情况下都有一行，要么用数字表示最低成本，要么包含"Impossible"一词。

样例 #1

样例输入 #1

3
1033 8179
1373 8017
1033 1033

样例输出 #1

6
7
0