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\nprime = [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)]\n\nx = (1, 2, 3, 4, 5, 6, 7, 8, 9)\n\navail = {x: 0}\nqueue = [x]\nwhile queue:\n    current = queue.pop(0)\n    for e in edges:\n        if current[e[0]] + current[e[1]] in prime:\n            nxt = list(current)\n            nxt[e[0]], nxt[e[1]] = nxt[e[1]], nxt[e[0]]\n            nxt = tuple(nxt)\n            if nxt not in avail:\n                avail[nxt] = avail[current] + 1 \n                queue.append(nxt)\n\nfor _ in range(int(input())):\n    input()\n    grid = ()\n    for i in range(3):\n        grid += tuple(map(int, input().split()))\n    print(avail[grid] if grid in avail else -1)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 35325302