{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"首相们对安全局长带来的消息感到非常不安，他们说他们将为了安全考虑改变首相房间门牌号上面的门牌号码。\u003cbr\u003e\n——要不时地改变门牌号，这样可以使敌人处于迷惑之中。\u003cbr\u003e\n——但是，我现在的门牌号是1033号，它是一个质数，我有质数强迫症。我不能忍受我的门牌号不是质数。\u003cbr\u003e\n——我知道，所以你的新门牌号8179号也是一个质数。你只需在你办公室的门上更换掉原来的四个数字就可以。\u003cbr\u003e\n——不，不是那么简单。假设我把第一个数字先改为8，那么在你更改下一个数字之前他将是8033，它不是素数！\u003cbr\u003e\n——我明白了，首相，即使在几秒钟内，你也不能忍受一个非质数。\u003cbr\u003e\n——是的！因此，你必须提出一种从1033改为8179而且中间全是质数的方案，每次只可以改变其中一个数位上的数字。\u003cbr\u003e\n\u003cbr\u003e\n例如：\u003cbr\u003e\n1033 \u003cbr\u003e\n1733 \u003cbr\u003e\n3733 \u003cbr\u003e\n3739 \u003cbr\u003e\n3779 \u003cbr\u003e\n8779 \u003cbr\u003e\n8179\u003cbr\u003e\n此时，我们一共更改了6次数字，已知更改一次数字需要花费1英镑，因此我们需要花费6英镑。\u003cbr\u003e\u003cbr\u003e\n你的任务就是写一个程序，对于任意的起始和终止数字，都求出最小花费。"}},{"title":"Input","value":{"format":"HTML","content":"输入数据有多组，首先是一个数字n，代表之后有n组数据。\u003cbr\u003e\n其次，在每一组输入中，都包含两个数字m和n，m代表原来的门牌号，n代表现在的门牌号。\u003cbr\u003e\n其中，m和n都是四位数，而且不含前导0。"}},{"title":"Output","value":{"format":"HTML","content":"每组输入输出一行，输出在此情况下的最小花费。若不存在从m到n的路径，则输出单词“Impossible”。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3\n1033 8179\n1373 8017\n1033 1033\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e6\n7\n0\u003c/pre\u003e"}}]}