省份 $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$。

输出格式

对于每个测试用例，在单独的一行中输出一个整数 — 必须保留的最少道路数量。

样例

输入样例 1

1
1
1

输出样例 1

0

输入样例 2

2
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
7
1 1 1 0 0 0 0
1 1 1 0 0 0 0
1 1 1 0 0 0 0
0 0 0 1 1 0 1
0 0 0 1 1 0 1
0 0 0 0 0 1 0
0 0 0 1 1 0 1

输出样例 2

3
4