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:

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
primes=set([2,3,5,7,11,13,17])
edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	li=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			li.append(int(j))
	li=tuple(li)
	# print(lis)
	if li in resource: print(resource[li])
	else:print(-1)

# cook your dish here
primes=set([2,3,5,7,11,13,17])

edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
edge=[(0,3),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8),(0,1),(1,2),(1,4)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	lis=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			lis.append(int(j))
	lis=tuple(lis)
	# print(lis)
	if lis in resource: print(resource[lis])
	else:print(-1)
			

primes=set([2,3,5,7,11,13,17])

edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
edge=[(0,3),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8),(0,1),(1,2),(1,4)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	lis=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			lis.append(int(j))
	lis=tuple(lis)
	# print(lis)
	if lis in resource: print(resource[lis])
	else:print(-1)
			

primes=set([2,3,5,7,11,13,17])

edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	lis=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			lis.append(int(j))
	lis=tuple(lis)
	# print(lis)
	if lis in resource: print(resource[lis])
	else:print(-1)
			

primes=set([2,3,5,7,11,13,17])
edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	lis=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			lis.append(int(j))
	lis=tuple(lis)
	# print(lis)
	if lis in resource: print(resource[lis])
	else:print(-1)
			

primes=set([2,3,5,7,11,13,17])

edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
edge=[(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(4,5),(3,6),(4,7),(5,8),(6,7),(7,8)]
x=list(range(1,10))
from collections import deque
queue=deque([x])
resource={tuple(x):0}
while queue:
	cur=queue.popleft()
	# print(cur)
	for ele in edge:
		if cur[ele[0]]+cur[ele[1]] in primes:
			curr=cur[0:]
			curr[ele[0]],curr[ele[1]]=curr[ele[1]],curr[ele[0]]
			
			ref=tuple(curr)
	
			if ref not in resource:
				resource[tuple(ref)]=resource[tuple(cur)]+1
				queue.append(curr)
			
for _ in range(int(input())):
	lis=[]
	line=input()
	for i in range(3):
		line=input()	
		
		for j in line.split():
			lis.append(int(j))
	lis=tuple(lis)
	# print(lis)
	if lis in resource: print(resource[lis])
	else:print(-1)
			

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
# print(avail)
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1# cook your dish here


# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
# print(avail)
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1# cook your dish here


# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
# print(avail)
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1# cook your dish here


# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
# print(avail)
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1# cook your dish here


# cook your dish here
prime = [2,3,5,7,11,13,17]
edges = [(0,3), (0,1), (1,2), (1,4), (2,5), (3,4), (3,6), (4,5), (4,7), (5,8), (6,7), (7,8)]

x = (1, 2, 3, 4, 5, 6, 7, 8, 9)

avail = {x: 0}
queue = [x]
while queue:
    current = queue.pop(0)
    for e in edges:
        if current[e[0]] + current[e[1]] in prime:
            nxt = list(current)
            nxt[e[0]], nxt[e[1]] = nxt[e[1]], nxt[e[0]]
            nxt = tuple(nxt)
            if nxt not in avail:
                avail[nxt] = avail[current] + 1 
                queue.append(nxt)

for _ in range(int(input())):
    input()
    grid = ()
    for i in range(3):
        grid += tuple(map(int, input().split()))
    print(avail[grid] if grid in avail else -1)

# cook your dish here
p = [2,3,5,7,11,13,17]
ed = [(0,3), (0,1), (1,2), (1,4), (2,5), (3,4), (3,6), (4,5), (4,7), (5,8), (6,7), (7,8)]

x = (1, 2, 3, 4, 5, 6, 7, 8, 9)

av = {x: 0}
qu = [x]
while qu:
    cur= qu.pop(0)
    for e in ed:
        if cur[e[0]] + cur[e[1]] in p:
            nxt = list(cur)
            nxt[e[0]], nxt[e[1]] = nxt[e[1]], nxt[e[0]]
            nxt = tuple(nxt)
            if nxt not in av:
                av[nxt] = av[cur] + 1 
                qu.append(nxt)

for _ in range(int(input())):
    input()
    grid = ()
    for i in range(3):
        grid += tuple(map(int, input().split()))
    print(av[grid] if grid in av else -1)

prime = [2,3,5,7,11,13,17]
edges = [(0,3), (0,1), (1,2), (1,4), (2,5), (3,4), (3,6), (4,5), (4,7), (5,8), (6,7), (7,8)]

x = (1, 2, 3, 4, 5, 6, 7, 8, 9)

avail = {x: 0}
queue = [x]
while queue:
    current = queue.pop(0)
    for e in edges:
        if current[e[0]] + current[e[1]] in prime:
            nxt = list(current)
            nxt[e[0]], nxt[e[1]] = nxt[e[1]], nxt[e[0]]
            nxt = tuple(nxt)
            if nxt not in avail:
                avail[nxt] = avail[current] + 1 
                queue.append(nxt)

for _ in range(int(input())):
    input()
    grid = ()
    for i in range(3):
        grid += tuple(map(int, input().split()))
    print(avail[grid] if grid in avail else -1)

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1# cook your dish here


# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

PRIMES = {3,5,7,11,13,17}

class Node :
    def __init__(self,string) :
        self.next = None
        self.a = string
    def swap(self,i,j) :
        b = self.a[:i] + self.a[j] + self.a[i+1:j] + self.a[i] + self.a[j+1:]
        return Node(b)
start_node = Node('123456789')

class Queue :
    def __init__(self) :
        self.front = None
        self.back = None
    def enqueue(self,node) :
        if self.back is None :
            self.front = self.back = node
        else :
            self.back.next = node
            self.back = node
    def dequeue(self) :
        if self.front is None :
            return None
        else :
            node = self.front
            self.front = node.next
            if self.front is None :
                self.back = None
            return node
q = Queue()
q.enqueue(start_node)

di = {start_node.a:0}
def bfs(q,level) :
    if q.front is None :
        return
    q2 = Queue()
    while q.front is not None :
        n = q.dequeue()
        for i in range(8) :
            # check right
            if i%3<2 :
                if int(n.a[i])+int(n.a[i+1]) in PRIMES :
                    b = n.swap(i,i+1)
                    if b.a not in di :
                        di[b.a] = level+1
                        q2.enqueue(b)
            # check down
            if i<6 :
                if int(n.a[i])+int(n.a[i+3]) in PRIMES :
                    b = n.swap(i,i+3)
                    if b.a not in di :
                        di[b.a] = level+1
                        q2.enqueue(b)
    bfs(q2,level+1)

bfs(q,0)
for _ in range(int(input())):
    input()
    # n,k = map(int,input().split())
    # s = sorted(map(int,input().split()),reverse=True)
    clue = ''
    for i in range(3) :
        clue += ''.join(input().split())
    print(di.get(clue,-1))


PRIMES = {3,5,7,11,13,17}

class Node :
    def __init__(self,string) :
        self.next = None
        self.a = string
    def swap(self,i,j) :
        b = self.a[:i] + self.a[j] + self.a[i+1:j] + self.a[i] + self.a[j+1:]
        return Node(b)
start_node = Node('123456789')

class Queue :
    def __init__(self) :
        self.front = None
        self.back = None
    def enqueue(self,node) :
        if self.back is None :
            self.front = self.back = node
        else :
            self.back.next = node
            self.back = node
    def dequeue(self) :
        if self.front is None :
            return None
        else :
            node = self.front
            self.front = node.next
            if self.front is None :
                self.back = None
            return node
q = Queue()
q.enqueue(start_node)

di = {start_node.a:0}
def bfs(q,level) :
    if q.front is None :
        return
    q2 = Queue()
    while q.front is not None :
        n = q.dequeue()
        for i in range(8) :
            # check right
            if i%3<2 :
                if int(n.a[i])+int(n.a[i+1]) in PRIMES :
                    b = n.swap(i,i+1)
                    if b.a not in di :
                        di[b.a] = level+1
                        q2.enqueue(b)
            # check down
            if i<6 :
                if int(n.a[i])+int(n.a[i+3]) in PRIMES :
                    b = n.swap(i,i+3)
                    if b.a not in di :
                        di[b.a] = level+1
                        q2.enqueue(b)
    bfs(q2,level+1)

bfs(q,0)
for _ in range(int(input())):
    input()
    # n,k = map(int,input().split())
    # s = sorted(map(int,input().split()),reverse=True)
    clue = ''
    for i in range(3) :
        clue += ''.join(input().split())
    print(di.get(clue,-1))


# cook your dish here
# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1

# cook your dish here
from collections import deque
primes = {2,3,5,7,11,13,17}
edges = [(0,3),(0,1),(1,2),(1,4),(2,5),(3,4),(3,6),(4,5),(4,7),(5,8),(6,7),(7,8)]
x = [1,2,3,4,5,6,7,8,9]
avail = {tuple(x):0}
q = deque([x])
while q:
    curr = q.popleft();
    for e in edges:
        if curr[e[0]]+curr[e[1]] in primes:
            nxt = curr[0:]
            nxt[e[0]],nxt[e[1]] = nxt[e[1]], nxt[e[0]] 
            nxtt = tuple(nxt)
            if nxtt not in avail:
                avail[nxtt] = avail[tuple(curr)]+1
                q.append(nxt)
t = int(input())
while t:
    inp = input()
    grid = []
    for i in range(3):
        inp = input()
        for j in inp.strip().split(" "):
            grid.append(int(j))
    gridt = tuple(grid)
    if gridt in avail: print(avail[gridt])
    else: print(-1);
    t-= 1