现给定两个 四位素数 $a, b$。 你可以执行多次下面的操作:
修改数字 $a$ 的某一位, 使其成为另一个 四位素数。
例如,$1033 \rightarrow 1\textbf{7}33$,其中 $1033$ 与 $1733$ 均为素数。
问至少多少次变换后能从 $a$ 得到 $b$ ? 或回答不可能。
数据规模
- 多组数据 $1 \le T \le 100$
输入格式
第一行一个数字 $T$,表示接下来将会有 $T$ 组数据。
接下来包含 $T$ 行,每行包含用空格分开的两个 四位素数 $a, b$。
输出格式
输出 $T$ 行,如果可以,输出最小变换次数。反之输出 $-1$。
样例输入
2
1033 1033
1033 8779
样例输出
0
5
说明
$$ 1033 \rightarrow 1\textbf{7}33 \rightarrow \textbf{3}733 \rightarrow 373\textbf{9} \rightarrow 37\textbf{7}9 \rightarrow \textbf{8}779 $$
tips: you only operate $8$ times if possible.