빨강 검정 징검다리

존과 베시가 방향 그래프에서 게임을 한다. 그래프는 두 사람 모두 알고 있다. 정점에는 $1$번부터 $n$번까지 번호가 붙어 있고, 정점 사이의 간선에는 방향이 있으며 각 간선은 빨간색이거나 검은색이다. 그래프와 별개로 크기가 $k$인 큐가 하나 있고, 큐에 든 색은 두 사람 모두 볼 수 있다.

게임을 시작할 때 존은 $1$번 정점에 말을 놓고 큐는 비어 있다. 베시가 큐를 빨간색과 검은색으로 가득 채우면 본 게임이 시작된다.

한 차례는 이렇게 진행된다.

1. 존이 큐의 맨 앞에서 색을 하나 꺼낸다.
2. 존은 말이 놓인 정점에서 나가는 간선 중 꺼낸 색과 같은 간선 하나를 골라 그 간선으로 말을 옮긴다. 자기 자신으로 돌아오는 간선을 골라도 된다.
3. 큐가 한 칸 비므로 베시가 큐의 끝에 색을 하나 채운다.

꺼낸 색과 같은 나가는 간선이 없어서 존이 말을 옮기지 못하면 베시가 이긴다. 존이 게임을 영원히 이어가면 존이 이긴다. 베시는 큐를 처음 채울 때도 매 차례 색을 채울 때도 존의 상황을 보고 색을 고르며, 존은 큐에 든 $k$개의 색을 모두 보고 간선을 고른다.

그래프가 주어질 때, 베시가 색을 어떻게 고르더라도 존이 이기는 큐의 최소 크기 $k$를 구하라.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 $n$ ($1 \le n \le 12$)이 주어진다. 이어지는 $n$개의 줄에는 빨간 간선의 인접 행렬이 주어진다. 각 줄에는 공백으로 구분된 $n$개의 정수가 있고, $i$번째 줄의 $j$번째 수가 $1$이면 $i$에서 $j$로 가는 빨간 간선이 있다는 뜻이고 $0$이면 없다는 뜻이다. 그다음 $n$개의 줄에는 같은 방식으로 검은 간선의 인접 행렬이 주어진다. 말의 시작 정점은 항상 $1$번이다.

존이 이길 수 있는 테스트 케이스에서 최소 $k$는 $12$ 이하이다.

각 테스트 케이스마다 존이 이기는 최소의 $k$를 한 줄에 출력한다. 큐의 크기를 얼마로 잡아도 존이 이길 수 없으면 $0$을 출력한다.