Prime Delight

Problem Description

You are given two four-digit prime numbers $a$ and $b$. You may perform the following operation multiple times:

Change one digit of $a$ so that it becomes another four-digit prime number.

For example, $1033 \rightarrow 1\mathbf{7}33$, where both $1033$ and $1733$ are prime.

What is the minimum number of transformations needed to turn $a$ into $b$? Or answer that it is impossible.

Input Format

The first line contains an integer $T$, indicating that $T$ groups of data follow.

The next $T$ lines each contain two four-digit primes $a, b$ separated by a space.

Output Format

Output $T$ lines. If possible, output the minimum number of transformations; otherwise output $-1$.

Sample Input

2
1033 1033
1033 8779

Sample Output

0
5

Sample Explanation

$$1033 \rightarrow 1\mathbf{7}33 \rightarrow \mathbf{3}733 \rightarrow 373\mathbf{9} \rightarrow 37\mathbf{7}9 \rightarrow \mathbf{8}779$$

Hint

If possible at all, you will need at most $8$ operations.

Constraints

• Multiple test cases, $1 \le T \le 100$