J10 实践-7 素数路径

题目描述

内阁的部长们对于安全部门首脑声称要改变他们办公室的 $4$ 个房间号非常烦恼。 —这只是一件安全措置，不时地改变这样的事物，使得敌人处于盲区。 — 但是你看，我已经选了我的房间号 1033 有很好的理由，我是总理，你知道的。 — 我知道的，所以你的新房间号 8179 也是素数，你只要在你的办公室房门上将这新的 $4$ 位数字贴在老的 $4$ 位数字上就可以了。 — 不，不那么简单。假如我把第一个数字改成 $8$，那么数字 8033 就不是素数！ — 我知道，作为总理，你不能忍受一个非素数作为你的房间号即使只有几秒钟。 — 正确！我必须找到一个从 1033 到 8179 的一个素数路径的方案，从一个素数到下一个素数只要改变一位数。 一直在听的财政部长，也介入了讨论。 — 请不要产生不必要的开支！我碰巧知道，改一位数字的价格是 $1$ 英镑。 — 在这种情况下，我需要一个计算机程序使得花费最小化，你知道有非常便宜的软件开发者吗？ — 我知道。有个程序设计竞赛马上要进行了。让他们帮助总理在两个四位素数之间找到最便宜的素数路径。当然，第一位是非零的。上述实例有个解答：

1033
1733
3733
3739
3779
8779
8179

这个解答花费 $6$ 英镑。注意第1个位置在第2步被粘贴，在最后一步不能被重用，在第 $1$ 个位置上要粘贴新值必须购买。

输入格式

第一行给出一个正整数：测试用例的数目（最多 $100$ ）。每个测试用例一行，两个用空格分开的数字，这两个数字都是 $4$ 位素数（不以 $0$ 作为首位）。

输出格式

对于每个测试用例，输出一行，或者是最小花费的数目，或者输出 "Impossible"。

样例输入

3
1033 8179
1373 8017
1033 1033

样例输出

6
7
0

样例分析

如上所述。

数据范围 对于 $100\%$ 的数据：如上所述。