import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

class State {
	public int number;
	public int[] array;
	public int[][] swapable;
}

public class Main {
	public static int ARRAY_SIZE = 9;
	static Map<Integer, Integer> visited = new HashMap<>();
	static Queue<State> queue = new LinkedList<>();

	private static boolean canSwap(int a, int b) {
		int c = a + b;
		if (c == 3 || c == 5 || c == 7 || c == 11 || c == 13 || c == 17)
			return true;
		return false;
	}

	public static int swap(int x, int y, int[] n) {
		int temp = n[x];
		n[x] = n[y];
		n[y] = temp;
		int sum = 0;
		for (int i = 0; i < ARRAY_SIZE; i++) {
			sum = 10 * sum + n[i];
		}
		return sum;
	}

	public static int[] copy(int[] a) {
		int[] c = new int[ARRAY_SIZE];
		for (int i = 0; i < ARRAY_SIZE; i++) {
			c[i] = a[i];
		}
		return c;
	}

	public static int[][] copy2d(int[][] a) {
		int[][] c = new int[ARRAY_SIZE][];
		for (int i = 0; i < ARRAY_SIZE; i++) {
			c[i] = new int[2];
			for (int j = 0; j < a[i].length; j++) {
				c[i][j] = a[i][j];
			}
		}
		return c;
	}

	public static int[][] updateswapable(int[] array) {
		int[][] swapability = { { 1, 3 }, { 2, 4 }, { 5 }, { 4, 6 }, { 5, 7 }, { 8 }, { 7 }, { 8 } };
		int[][] x = new int[][] { { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 }, { -1, -1 },
				{ -1, -1 } };
		for (int i = 0; i < swapability.length; i++) {
			for (int j = 0; j < swapability[i].length; j++) {
				if (canSwap(array[i], array[swapability[i][j]]))
					x[i][j] = swapability[i][j];
			}
		}
		return x;
	}

	public static void generateStates(State s, int level) {
		queue.add(s);
		visited.put(s.number, 0);
		while (queue.size() > 0) {
			State parent = queue.remove();
			level = visited.get(parent.number) + 1;
			// System.out.println("removed"+parent.number);
			for (int i = 0; i < ARRAY_SIZE - 1; i++) {
				for (int j = 0; j < parent.swapable[i].length; j++) {
					if (parent.swapable[i][j] < 0) {
						continue;
					}
					State child = new State();
					child.array = copy(parent.array);
					child.number = swap(i, parent.swapable[i][j], child.array);
					if (!visited.containsKey(child.number)) {
						child.swapable = updateswapable(child.array);
						// child.level = parent.level + 1;
						visited.put(child.number, level);
						// System.out.println("adding "+child.number);
						queue.add(child);
					}

				}
			}
		}
	}

	public static void main(String args[]) throws Exception {
		State initstate = new State();
		initstate.number = 123456789;
		initstate.array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		initstate.swapable = new int[][] { { 1, 3 }, { 2, 4 }, { -1, -1 }, { 6, -1 }, { 5, 7 }, { -1, -1 }, { -1, -1 },
				{ 8, -1 } };
		generateStates(initstate, 0);
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(r.readLine());
		for (int i = 0; i < n; i++) {
			int num = 0;
			r.readLine();
			String in;
			in = r.readLine();
			in = in + " " + r.readLine();
			in = in + " " + r.readLine();
			StringTokenizer st = new StringTokenizer(in, " ");
			while (st.hasMoreTokens()) {
				num = num * 10 + Integer.parseInt(st.nextToken());
			}
			System.out.println(visited.get(num) != null ? (int) visited.get(num) : -1);
		}

	}
}