Responsive image

问题 D: 素数

问题 D: 素数

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 10
[提交][状态][讨论版][命题人:]

题目描述

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

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

例如，1033→17331033→1733，其中 10331033 与 17331733 均为素数。 

问至少多少次变换后能从 aa 得到 bb ? 或回答不可能。 

输入描述

第一行一个数字 TT，表示接下来将会有 TT 组数据。

接下来包含 TT 行，每行包含用空格分开的两个 四位素数 a,ba,b。
       输出 T 行，如果可以，输出最小变换次数。反之输出 −1。

输出描述

输出 T 行，如果可以，输出最小变换次数。反之输出 −1。

样例输入

2
1033 1033
1033 8779

样例输出

0
5

提示

1033-->1733-->3733-->3739-->3779-->8779

[提交][状态]
ACM算法攻关部