시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
9 초 256 MB 2 2 2 100.000%

문제

존과 베시는 방향성 그래프 위에서 게임을 하고 있으며, 둘 다 그래프의 생김새를 알고 있다. 그래프는 1 부터 n까지 차례차례 이름붙여진 n개의 정점으로 이뤄져 있으며 정점 사이에는 방향성 간선들이 존재한다. 각각의 간선은 빨간색 혹은 검정색으로 색칠되어있다. 그리고 그래프와는 별개로 양쪽 모두에게 내용물이 보이는 크기 k의 큐가 존재한다. 게임 시작시에 존은 1번 정점에 게임 말을 두고, 큐는 비어있다. 그 후 베시는 큐가 가득 찰 때까지 큐에 빨간색 혹은 검정색을 집어넣는다. 그 후 메인 게임이 시작된다.

존은 큐의 제일 앞에서 색을 하나 꺼낸 뒤, 현재 위치한 정점에서 나가는 간선 중 꺼낸 색과 같은 간선을 하나 골라 해당 간선을 타고 게임 말을 이동시킨다(간선으로 타고 이동한 결과 자기 자신에게 돌아올 수도 있다!). 그럼 큐가 한 칸 비게 되는데, 베시는 큐의 끝에 새로운 색을 채워넣는다.

이와 같은 행동을 반복하며 게임은 진행된다.

베시는 존이 더 이상 말을 움직일 수 없게 된다면 승리한다(같은 색의 나가는 간선을 선택할 수 없어서). 만약 게임을 영원히 계속할 수 있다면 존이 승리한다.

그래프의 형태가 주어질 때, 존이 항상 승리하기 위해서 필요한 큐의 최소 사이즈 k를 출력하라.

입력

첫 줄에는 테스트 케이스의 개수 정수 t(1 <= t <= 20)가 주어진다.

각각의 테스트 케이스는 첫 줄에 그래프 정점의 개수 정수 n(1 <= n <= 12)가 주어진다. 이어지는 n줄은 n개의 공백으로 구분된 정수가 주어지며, i번째 줄의 j번째 숫자가 1이라면 i에서 j로 향하는 빨간 간선이 존재한다는 뜻이고 0이면 존재하지 않는다는 뜻이다. 그 뒤 이어지는 n줄은 역시 n개의 공백으로 구분된 정수가 주어지며, i번째 줄의 j번째 숫자가 1이라면 i에서 j로 향하는 검은 간선이 존재한다는 뜻이고 0이면 존재하지 않는다는 뜻이다. 언제나 시작정점은 1번이다.

출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 존이 이길 수 있는 최소의 k를 출력한다. 만약 어떤 사이즈의 큐가 있더라도 존이 이길 수 없다면 0을 출력한다.

예제 입력

3
3
1 0 0
1 0 0
0 0 0
0 1 1
0 0 0
1 0 0
1
1
1
2
0 1
1 0
0 0
0 1

예제 출력

2
1
0

힌트