Red and Black Stepping Stones

John and Bessie play a game on a directed graph, and both of them know the graph. The vertices are numbered $1$ through $n$, the edges between vertices have a direction, and every edge is red or black. Apart from the graph there is one queue of size $k$, and both players see the colors inside it.

At the start John puts his piece on vertex $1$ and the queue is empty. Bessie fills the queue with red and black colors until it is full, and then the main game begins.

A turn runs like this.

1. John removes one color from the front of the queue.
2. John picks an outgoing edge of that color at the vertex where his piece stands, and moves the piece along that edge. He may pick an edge that leads back to the same vertex.
3. One slot of the queue is now empty, so Bessie appends one color at the back.

Bessie wins if John cannot move his piece because his vertex has no outgoing edge of the color he removed. John wins if he keeps the game going forever. Bessie sees John's situation both when she first fills the queue and when she appends a color on a turn, and John sees all $k$ colors in the queue when he picks an edge.

Given the graph, find the smallest queue size $k$ for which John wins no matter how Bessie picks colors.

The first line has the number of test cases $t$ ($1 \le t \le 20$).

The first line of each test case has the number of vertices $n$ ($1 \le n \le 12$). The next $n$ lines hold the adjacency matrix of the red edges. Each line has $n$ integers separated by spaces, and the $j$-th number on the $i$-th line is $1$ if there is a red edge from $i$ to $j$ and $0$ if there is none. The next $n$ lines hold the adjacency matrix of the black edges in the same format. The piece always starts on vertex $1$.

In every test case where John can win, the smallest $k$ is at most $12$.

For each test case print the smallest $k$ for which John wins on its own line. If John cannot win for any queue size, print $0$.