도로변 최적화

지방 $G$의 일부 마을은 도로로 연결되어 있으며, 도로는 항상 양방향으로 통행할 수 있다. 도로망을 유지할 예산이 부족하여, 최소한의 도로만 남기기로 결정했다. 다만 현재 마을 $A$에서 마을 $B$로 갈 수 있다면, 도로를 줄인 뒤에도 그 가능성은 유지되어야 한다.

남겨야 하는 도로의 최소 개수를 구하시오.

입력 파일의 첫 번째 줄에는 테스트의 수 $T$가 주어진다 ($1 \le T \le 50\,000$). 이어서 $T$개의 테스트에 대한 설명이 주어진다.

$t$번째 테스트의 첫 번째 줄에는 마을의 수 $N_t$가 주어진다 ($1 \le N_t \le 200$).

다음 $N_t$개의 줄에는 $N_t$개의 정수가 주어지며, 각 정수는 $0$ 또는 $1$이다. $i$번째 줄의 $j$번째 위치가 $0$이면 마을 $i$에서 마을 $j$로 갈 수 없고(다른 마을을 거쳐서도 갈 수 없다), $1$이면 통로가 있다. 마을에서 자기 자신으로 가는 통로가 있다고 가정하므로, $i$번째 줄의 $i$번째 위치에는 항상 $1$이 있다 ($1 \le i \le N_t$).

모든 테스트에 대한 $N_t^2$의 합은 $50\,000$ 이하임이 보장된다.

각 테스트마다 남겨야 하는 도로의 최소 개수를 한 줄에 하나씩 출력한다.