// Arup Guha
// 5/15/2017
// Solution to 2014 NAQ Problem B: Color Walk

import java.util.*;

public class colorwalk {

	public static int n;
	public static ArrayList[] red;
	public static ArrayList[] black;

	public static boolean[] safe;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

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

			n = stdin.nextInt();
			red = new ArrayList[n];
			black = new ArrayList[n];

			// Read in red graph.
			for (int i=0; i<n; i++) {
				red[i] = new ArrayList<Integer>();
				for (int j=0; j<n; j++) {
					int tmp = stdin.nextInt();
					if (tmp == 1)
						red[i].add(j);
				}
			}

			// Read in black graph.
			for (int i=0; i<n; i++) {
				black[i] = new ArrayList<Integer>();
				for (int j=0; j<n; j++) {
					int tmp = stdin.nextInt();
					if (tmp == 1)
						black[i].add(j);
				}
			}

			// Solve it!
			System.out.println(solve());
		}
	}

	public static int solve() {

		for (int i=1; i<=n; i++) {
			boolean tmp = solve(i);
			if (tmp) return i;
		}

		// Nothing worked, so Bob always wins.
		return 0;
	}

	public static boolean solve(int qSize) {

		Boolean[][] res = new Boolean[n][1<<qSize];
		for (int i=0; i<n; i++) Arrays.fill(res[i], null);

		// Iterate as long as we're adding new states that Bob wins.
		while (round(qSize, res) > 0);

		// If there's any state starting at vertex 0 that Bob gets, then he wins.
		for (int i=0; i<(1<<qSize); i++)
			if (res[0][i] != null && res[0][i] == false)
				return false;

		// If there isn't, Alice wins.
		return true;
	}


	public static int round(int qSize, Boolean[][] res) {

		int changeF = 0, maxMask = (1<<qSize) - 1;

		// Loop through our state space.
		for (int v=0; v<n; v++) {
			for (int queue=0; queue<(1<<qSize); queue++) {

				// Can't change.
				if (res[v][queue] != null) continue;

				boolean nextRed = ((queue >> (qSize-1)) == 0);
				ArrayList<Integer> nextV = new ArrayList<Integer>();

				// List next possible destinations.
				if (nextRed) for (int i=0; i<red[v].size(); i++) nextV.add(((ArrayList<Integer>)red[v]).get(i));
				else         for (int i=0; i<black[v].size(); i++) nextV.add(((ArrayList<Integer>)black[v]).get(i));

				int falseCnt = 0;

				// Go to all possible next vertices.
				for (int i=0; i<nextV.size(); i++) {

					int nextNode = nextV.get(i);

					// See if either of these states is a losing state. If so, Bob could put us there.
					for (int j=0; j<2; j++) {
						Boolean tmp = res[nextNode][maxMask & ((queue << 1)+j)];
						if (tmp != null && tmp == false) {
							falseCnt++;
							break;
						}
					}
				}

				// If, for each option, Bob could put us in a losing state, this is a losing state also.
				if (falseCnt == nextV.size()) {
					res[v][queue] = false;
					changeF++;
				}
			}
		}

		// The number of states that changed to losing states on this iteration.
		return changeF;
	}
}