题目描述

给你两个素数，请问，你能否从第一个变换到第二个？变换规则如下：

• 每次将当前素数的某一位换掉，成为一个新的素数。 比如，要从 $1033$ 变到 $8179$，可以如下操作：

$1033→1733→3733→3739→3779→8779→8179$

输入格式

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

输出格式

每个测试用例输出一行，如果可以变形成功，输出最少的变换次数；否则输出Impossible。

样例

3
1033 8179
1373 8017
1033 1033

6
7
0

提示