Roadside optimization

Some towns in the province $G$ are connected by roads, and roads always run both ways. The budget for maintaining the road network is scarce, so it was decided to keep only the minimum number of roads. However, if it is currently possible to reach town $B$ from town $A$, this must remain possible even after the reduction.

Determine the minimum number of roads that must be kept.

The first line of the input file contains a single integer $T$, the number of tests ($1 \le T \le 50\,000$). The descriptions of $T$ tests follow.

The first line of test $t$ contains a single integer $N_t$, the number of towns ($1 \le N_t \le 200$).

The next $N_t$ lines contain $N_t$ integers each, and every integer is either $0$ or $1$. If the $j$th position of line $i$ is $0$, then town $j$ cannot be reached from town $i$ (not even by passing through other towns); if it is $1$, then there is a passage. A passage from a town to itself is assumed, so the $i$th position of line $i$ is always $1$ ($1 \le i \le N_t$).

The sum of $N_t^2$ over all tests is guaranteed not to exceed $50\,000$.

For each test, print the minimum number of roads to be kept on a separate line.