동굴

카프카스 산맥에 있는 크루베라 동굴은 여러 방(chamber)을 잇는 거대한 균열들의 미로이다. 세계에서 가장 깊은 이 동굴(깊이 1710미터)을 탐사하던 도중 사고가 발생하여 탐험대원 한 명이 실종되었다. 실종 사실은 모든 대원이 동굴을 빠져나온 뒤에야 밝혀졌고, 동굴의 규모를 생각하면 한시가 급했다. 그래서 동굴의 모든 방을 수색하는 구조 작업을 벌이기로 했다.

각 방은 서로 다른 깊이에 있다. 일부 방들은 균열로 연결되어 있으며, 각 균열은 정확히 두 방을 잇는다. 구조에 참여하는 구조대원은 동굴의 입구 방 중 하나를 골라 밧줄을 타고 항상 아래 방향으로만 내려가며, 지나는 방들 중 일부(혹은 전부)를 수색할 수 있다. 한 방은 여러 구조대원이 중복해서 수색해도 된다. 모든 방을 수색하는 데 필요한 구조대원의 최소 인원수를 구하여라.

첫 줄에 데이터 세트의 개수 $z$가 주어진다. 이어서 $z$개의 데이터 세트가 차례로 주어진다. 각 데이터 세트의 형식은 다음과 같다.

첫 줄에 방의 개수 $n$ ($1 \le n \le 1200$)이 주어진다. 이어지는 $n$개의 줄에는 각각 길이 $n$인 0과 1로 이루어진 문자열이 주어진다. $i$번째 줄의 $j$번째 문자가 1이면, $i$번 방이 $j$번 방보다 위에 있으며 $i$번 방에서 (도중에 다른 방들을 지날 수도 있지만) 밧줄을 타고 내려가 $j$번 방에 도달할 수 있음을 뜻한다. 0이면 $i$번 방에서 내려가는 방향으로 $j$번 방에 도달할 수 없음을 뜻한다. 위에서 내려오는 균열이 하나도 없는 방(즉 어떤 방에서도 도달할 수 없는 방)을 입구 방으로 본다.

각 데이터 세트마다, 모든 방을 수색하는 데 필요한 구조대원의 최소 인원수 $k$를 한 줄에 하나씩 출력한다.