namespace CodeChef
{
class Program
{
static int[] move1 = new int[] { 0, 1, 3, 4, 6, 7, 0, 1, 2, 3, 4, 5 };
static int[] move2 = new int[] { 1, 2, 4, 5, 7, 8, 3, 4, 5, 6, 7, 8 };

static void Main(string[] args)
{

int times = int.Parse(Console.ReadLine());

for (int i = 0; i < times; i++)
{
int[] board = new int[9];
string[] s;
Console.ReadLine();
s = Console.ReadLine().Split(' ');
board[0] = int.Parse(s[0]);
board[1] = int.Parse(s[1]);
board[2] = int.Parse(s[2]);
s = Console.ReadLine().Split(' ');
board[3] = int.Parse(s[0]);
board[4] = int.Parse(s[1]);
board[5] = int.Parse(s[2]);
s = Console.ReadLine().Split(' ');
board[6] = int.Parse(s[0]);
board[7] = int.Parse(s[1]);
board[8] = int.Parse(s[2]);

int d = Search(board);
Console.WriteLine(d);
}
}

static int Search(int[] board)
{
Board b = new Board(0, board);
HashSet seen = new HashSet();
Queue bs = new Queue();

bs.Enqueue(b);
while (bs.Count > 0)
{
Board b1 = bs.Dequeue();
//Console.WriteLine(b1.ToString());
if (Board.Test(b1))
{
return b1.Depth;
}

for (int k = 0; k < move1.Length; k++)
{
int i = move1[k];
int j = move2[k];
if (Board.CanSwap(b1, i, j))
{
Board b2 = Board.Swap(b1, i, j);
if (!seen.Contains(b2))
{
seen.Add(b2);
bs.Enqueue(b2);
}
}
}
}

return -1;
}

class Board
{
static HashSet primes = new HashSet();

public override string ToString()
{
return
Depth + "\n" +
string.Format("{0} {1} {2}\n", _board[0], _board[1], _board[2]) +
string.Format("{0} {1} {2}\n", _board[3], _board[4], _board[5]) +
string.Format("{0} {1} {2}\n", _board[6], _board[7], _board[8]);
}
int[] _board;
public int Depth;

public Board(int d, int[] b)
{
_board = (int[])b.Clone();
Depth = d;
}

static Board()
{
primes.Add(3); primes.Add(5); primes.Add(7); primes.Add(11); primes.Add(13); primes.Add(17);
}

public static bool CanSwap(Board b, int i, int j)
{
return primes.Contains(b._board[i] + b._board[j]);
}

public static Board Swap(Board b, int i, int j)
{
Board b2 = new Board(b.Depth + 1, b._board);
int temp = b2._board[i];
b2._board[i] = b2._board[j];
b2._board[j] = temp;
return b2;
}

public static bool Test(Board b)
{
return b._board[0] == 1 &&
b._board[1] == 2 &&
b._board[2] == 3 &&
b._board[3] == 4 &&
b._board[4] == 5 &&
b._board[5] == 6 &&
b._board[6] == 7 &&
b._board[7] == 8 &&
b._board[8] == 9;
}

public override bool Equals(object obj)
{
var b = obj as Board;

if (b == null)
return false;

return b._board[0] == _board[0]
&& b._board[1] == _board[1]
&& b._board[2] == _board[2]
&& b._board[3] == _board[3]
&& b._board[4] == _board[4]
&& b._board[5] == _board[5]
&& b._board[6] == _board[6]
&& b._board[7] == _board[7]
&& b._board[8] == _board[8]
;
}

public override int GetHashCode()
{
return _board[0].GetHashCode()
^ _board[1].GetHashCode()
^ _board[2].GetHashCode()
^ _board[3].GetHashCode()
^ _board[4].GetHashCode()
^ _board[5].GetHashCode()
^ _board[6].GetHashCode()
^ _board[7].GetHashCode()
^ _board[8].GetHashCode()
;
}
}
}
}