class puzzle
{
int matrix[3][3];
int prime[19];
int solved[3][3];
int count[50];
public:
puzzle(int number)
{
for (int i = 0; i < 19; i++)
prime[i] = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
solved[i][j] = i * 3 + j + 1;
for (int i = 0; i < number; i++)
count[i] = 0;
}
void scan(void)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
std::cin >> matrix[i][j];
}
void solve(int test_case)
{
bool done = false;
int temp;
int correct_location_j, correct_location_i;
int current;
//display();
this->scan();
int iteration = 2;
while (iteration--)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (matrix[i][j] != solved[i][j])
{
temp = matrix[i][j];
correct_location_i = correct_i(temp);
correct_location_j = correct_j(temp);
int current_row, current_col;
for (current_row = i; current_row != correct_location_i; )
{
if (current_row < correct_location_i)
{
if (current_row + 1 < 3)
{
// if (matrix[i + 1][j] != solved[i + 1][j])
if (prime[matrix[current_row + 1][j] + matrix[current_row][j]] == 0)
{
swap(current_row, j, current_row + 1, j, test_case);
}
else
break;
current_row++;
}
}
else if (current_row >= correct_location_i)
{
if (current_row - 1 >= 0)
{
//if (matrix[i - 1][j] != solved[i - 1][j])
if (prime[matrix[current_row - 1][j] + matrix[current_row][j]] == 0)
swap(current_row, j, current_row - 1, j, test_case);
else
break;
current_row--;
}
}
}
for (current_col = j; current_col != correct_location_j; )
{
if (current_col < correct_location_j)
{
if (current_col + 1 < 3)
{
//if (matrix[i][j + 1] != solved[i][j + 1])
if (prime[matrix[current_row][current_col + 1] + matrix[current_row][current_col]] == 0)
swap(current_row, current_col, current_row, current_col + 1, test_case);
else
break;
current_col++;
}
}
else if (current_col > correct_location_j)
{
if (current_col - 1 >= 0)
{
//if (matrix[i][j - 1] != solved[i][j - 1])
if (prime[matrix[current_row][current_col - 1] + matrix[current_row][current_col]] == 0)
swap(current_row, current_col, current_row, current_col - 1, test_case);
else
break;
current_col--;
}
}
}
}
done = check_solved();
if (done)
break;
}
if (done)
break;
}
if (done)
break;
}
if (done == false)
count[test_case] = -1;
}
void display_count(int test_case)
{
for (int i = 0; i < test_case; i++)
std::cout << count[i] << std::endl;
}
bool check_solved(void)
{
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (matrix[i][j] != solved[i][j])
return false;
}
}
return true;
}
int correct_j(int value)
{
int temp = value % 3;
if (temp == 1) return 0;
else if (temp == 2) return 1;
else if (temp == 0) return 2;
}
int correct_i(int value)
{
if (value >= 1 && value <= 3)
return 0;
else if (value >= 4 && value <= 6)
return 1;
else if (value >= 7 && value <= 9)
return 2;
}
void generate_prime(void)
{
for (int i = 2; i < 19; i++)
{
if (prime[i] == 0)
{
int temp = 2;
for (int j = i + i; j < 19; j = i * temp, temp++)
{
prime[j] = 1;
}
}
}
}
int swap(int first_row, int first_coloumn, int second_row, int second_coloumn, int test_case)
{
int temp = matrix[first_row][first_coloumn];
matrix[first_row][first_coloumn] = matrix[second_row][second_coloumn];
matrix[second_row][second_coloumn] = temp;
count[test_case]++;
return 1;
}
};
int main()
{
//Scanning test cases
int test_case = 0;
std::cin >> test_case;
puzzle ob(test_case);
ob.generate_prime();
int iterating = test_case, current = test_case;
while (iterating > 0)
{
ob.solve(current = test_case - iterating);
iterating--;
}
ob.display_count(test_case);
//getchar();
// getchar();
}