素数之欢

题目描述

现给定两个 四位素数 $a, b$。 你可以执行多次下面的操作：

修改数字 $a$ 的某一位, 使其成为另一个 四位素数。

例如，$1033 \rightarrow 1\textbf{7}33$，其中 $1033$ 与 $1733$ 均为素数。

问至少多少次变换后能从 $a$ 得到 $b$ ? 或回答不可能。

输入格式

第一行一个数字 $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.

数据范围

• 多组数据 $1 \le T \le 100$