// Arup Guha
// 12/17/2012
// Solution to 2010 Mercer Contest Problem The 8-Puzzle(prob8)
// Edited on 7/18/2016 to include DX, DY arrays.

import java.util.*;

public class puzzle {

	// Winning board
	public final static int WIN = 123456780;
	
	// Directions of movement for swaps.
	final public static int[] DX = {-1,0,0,1};
	final public static int[] DY = {0,-1,1,0};
	
	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		// Store all reachable boards in this table.
		HashMap<Integer,Integer> table = new HashMap<Integer,Integer>();

		// Start from the winning position and search out, storing all answers
		// before reading in the cases.
		table.put(WIN, 0);
		solve(table);

		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=0; loop<numCases; loop++) {

			int[] board = new int[9];
			for (int i=0; i<9; i++)
				board[i] = stdin.nextInt();
			
			// Just look it up - solution is guaranteed by specification.
			System.out.println(table.get(hashCode(board)));
		}
	}

	// Runs a BFS from the winning board and stores all reachable boards and number of steps in table.
	// Note: If I properly planned this, I probably would have returned the table.
	public static void solve(HashMap<Integer,Integer> table) {

		// Queue for BFS.
		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.offer(WIN);

		while (queue.size() != 0) {

			// Get the next board.
			int val = queue.poll();
			int curMoves = table.get(val);

			// Loop through adjacent boards, adding into the queue if they weren't previously there.
			ArrayList<Integer> next = getNext(val);
			for (int i=0; i<next.size(); i++) {

				if (!table.containsKey(next.get(i))) {
					table.put(next.get(i), curMoves+1);
					queue.offer(next.get(i));
				}

			}
		}
	}

	// Returns an int representation of a single board.
	public static int hashCode(int[] board) {
		int sum = 0;
		for (int i=0; i<9; i++)
			sum = 10*sum + board[i];
		return sum;
	}

	// Creates a board from a single value.
	public static int[] makeBoard(int val) {

		// Parse out each digit, storing backwards.
		int[] ans = new int[9];
		for (int i=8; i>=0; i--) {
			ans[i] = val%10;
			val /= 10;
		}
		return ans;
	}

	// Return all adjacent board positions to val.
	public static ArrayList<Integer> getNext(int val) {

		// Find the location with the zero.
		int[] copy = makeBoard(val);
		int place = 8;
		while (val%10 != 0) {
			place--;
			val /= 10;
		}

		// Extract row and column of empty square.
		int row = place/3;
		int col = place%3;
		ArrayList<Integer> ans = new ArrayList<Integer>();
		
		// Try each direction.
		for (int i=0; i<DX.length; i++) {
			
			// See what we would swap with.
			int swapX = row + DX[i];
			int swapY = col + DY[i];
			if (!inbounds(swapX, swapY)) continue;
			
			// As long as it's inbounds, it's a viable swap.
			swap(copy, row, col, swapX, swapY);
			ans.add(hashCode(copy));
			swap(copy, row, col, swapX, swapY);
		}

		// Return our list.
		return ans;
	}
	
	public static boolean inbounds(int x, int y) {
		return x >= 0 && x < 3 && y >= 0 && y < 3;
	}

	// Swaps locations (r1,c1) and (r2,c2) in board.
	public static void swap(int[] board, int r1, int c1, int r2, int c2) {
		int temp = board[3*r1+c1];
		board[3*r1+c1] = board[3*r2+c2];
		board[3*r2+c2] = temp;
	}
}