Johnny has some difficulty memorizing the small prime numbers. So, his computer science teacher has asked him to play with the following puzzle game frequently.
The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective of the puzzle is to swap the tiles until the following final state is reached:
1 2 3
4 5 6
7 8 9

At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.
Help Johnny to find the shortest number of steps needed to reach the goal state.

-----Input-----
The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle which Johnny would like to solve.
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 solve the corresponding puzzle. If there is no way to reach the final state, print the number -1.

-----Example-----
Input:
2

7 3 2 
4 1 5 
6 8 9 

9 8 5 
2 4 1 
3 7 6  

Output:
6
-1

-----Output details-----
The possible 6 steps in the first test case are described in the following figure:

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'primes=set([2,3,5,7,11,13,17])\n\nedge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]\nedge=[(0,3),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8),(0,1),(1,2),(1,4)]\nx=list(range(1,10))\nfrom collections import deque\nqueue=deque([x])\nresource={tuple(x):0}\nwhile queue:\n\tcur=queue.popleft()\n\t# print(cur)\n\tfor ele in edge:\n\t\tif cur[ele[0]]+cur[ele[1]] in primes:\n\t\t\tcurr=cur[0:]\n\t\t\tcurr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]\n\t\t\t\n\t\t\tref=tuple(curr)\n\t\n\t\t\tif ref not in resource:\n\t\t\t\tresource[tuple(ref)]=resource[tuple(cur)]+1\n\t\t\t\tqueue.append(curr)\n\t\t\t\nfor _ in range(int(input())):\n\tlis=[]\n\tline=input()\n\tfor i in range(3):\n\t\tline=input()\t\n\t\t\n\t\tfor j in line.split():\n\t\t\tlis.append(int(j))\n\tlis=tuple(lis)\n\t# print(lis)\n\tif lis in resource: print(resource[lis])\n\telse:print(-1)\n\t\t\t'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 35504336