每次操作可以把一个四位数中的一位数字改成另一个数字。操作前后都必须是四位质数，并且千位不能改为 0。

给出若干组起点和终点，求从起点质数变为终点质数所需的最少操作次数。

输入格式

第一行一个整数 $T$，表示测试用例数，$T\le100$。

接下来 $T$ 行，每行两个四位质数。

输出格式

对每组数据输出一行。若能够到达，输出最少操作次数；否则输出 Impossible。

3
1033 8179
1373 8017
1033 1033

6
7
0

1
8179 8179

0

2
7129 6007
6947 7933

5
4