Mr. Bond was enjoying his vacations in old palace of Scotland where he found a golden chest. The chest had a 3x3 security board which had numbers 1 to 9 uniquely written over it in an arbitrary order. The chest would only open when the security board has numbers written on it in the order as shown below:-

1 2 3

4 5 6

7 8 9

The problem of the security board is that the two numbers on it can be swapped only if they are adjacent and their sum is a prime number. Now, Bond wants you to help him in finding the minimum number of swaps needed to reveal the mystery behind the chest.

Input

The first line contains t, the number of test cases. Then t test cases follow. Each test case consists of a 3x3 table which will have numbers from 1 to 9.

The input data for successive test cases is separated by a blank line.

Output

For each test case print a single line containing the shortest number of steps needed to unlock the mystery behind the chest. If there is no way to unlock the mystery, print the number -1.