题目描述

Smart 住在 Sarah 大街 \(a\) 号，\(a\) 是一个 \(4\) 位的素数，他想去 Sarah 大街 \(b\) 号吃饭，\(b\) 也是一个素数，Sarah 大街很奇怪，没有马路，只有传送门，从 \(a\) 号出发，按下按钮会修改修改其中的一个数字，使它变成另外一个素数 \(a_1\)，继续这样，\(a_2,a_3,…\)，直到变成 \(b\)。求 Smart 按下按钮的最少次数。

例如，将 \(1033\) 变为 \(8179\)，最少需要按下 \(6\) 次按钮，具体操作为：

\(1033 -> 1733 -> 3733 -> 3739 -> 3779 -> 8779 -> 8179\)

格式

输入格式

第一行是正整数 \(t(≤100)\)，表示数据组数；接下来 \(t\) 行，每行两个 \(4\) 位的素数。

输出格式

对于每组数据，输出最短按下按钮的次数。

样例1

样例输入1

3
1033 8179
1373 8017
1033 1033

样例输出1

6
7
0

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T4\)