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 = {3,5,7,11,13,17}\r\n\r\nclass Node :\r\n    def __init__(self,string) :\r\n        self.next = None\r\n        self.a = string\r\n    def swap(self,i,j) :\r\n        b = self.a[:i] + self.a[j] + self.a[i+1:j] + self.a[i] + self.a[j+1:]\r\n        return Node(b)\r\nstart_node = Node('123456789')\r\n\r\nclass Queue :\r\n    def __init__(self) :\r\n        self.front = None\r\n        self.back = None\r\n    def enqueue(self,node) :\r\n        if self.back is None :\r\n            self.front = self.back = node\r\n        else :\r\n            self.back.next = node\r\n            self.back = node\r\n    def dequeue(self) :\r\n        if self.front is None :\r\n            return None\r\n        else :\r\n            node = self.front\r\n            self.front = node.next\r\n            if self.front is None :\r\n                self.back = None\r\n            return node\r\nq = Queue()\r\nq.enqueue(start_node)\r\n\r\ndi = {start_node.a:0}\r\ndef bfs(q,level) :\r\n    if q.front is None :\r\n        return\r\n    q2 = Queue()\r\n    while q.front is not None :\r\n        n = q.dequeue()\r\n        for i in range(8) :\r\n            # check right\r\n            if i%3<2 :\r\n                if int(n.a[i])+int(n.a[i+1]) in PRIMES :\r\n                    b = n.swap(i,i+1)\r\n                    if b.a not in di :\r\n                        di[b.a] = level+1\r\n                        q2.enqueue(b)\r\n            # check down\r\n            if i<6 :\r\n                if int(n.a[i])+int(n.a[i+3]) in PRIMES :\r\n                    b = n.swap(i,i+3)\r\n                    if b.a not in di :\r\n                        di[b.a] = level+1\r\n                        q2.enqueue(b)\r\n    bfs(q2,level+1)\r\n\r\nbfs(q,0)\r\nfor _ in range(int(input())):\r\n    input()\r\n    # n,k = map(int,input().split())\r\n    # s = sorted(map(int,input().split()),reverse=True)\r\n    clue = ''\r\n    for i in range(3) :\r\n        clue += ''.join(input().split())\r\n    print(di.get(clue,-1))\r\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 21832668