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 = '# cook your dish here\n# cook your dish here\nfrom collections import deque\nprimes = {2,3,5,7,11,13,17}\nedges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]\nx = [1,2,3,4,5,6,7,8,9]\navail = {tuple(x):0}\nq = deque([x])\nwhile q:\n    curr = q.popleft();\n    for e in edges:\n        if curr[e[0]]+curr[e[1]] in primes:\n            nxt = curr[0:]\n            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] \n            nxtt = tuple(nxt)\n            if nxtt not in avail:\n                avail[nxtt] = avail[tuple(curr)]+1\n                q.append(nxt)\nt = int(input())\nwhile t:\n    inp = input()\n    grid = []\n    for i in range(3):\n        inp = input()\n        for j in inp.strip().split(" "):\n            grid.append(int(j))\n    gridt = tuple(grid)\n    if gridt in avail: print(avail[gridt])\n    else: print(-1);\n    t-= 1'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 35504558