当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小蓝正在玩一款游戏，游戏中有一个 $n×n$ 大小的 01 矩阵 $A_{i,j}$。 小蓝每次需要选择一个 $T$ 字型的区域，且这个区域内至少要有一个 1。选中后，这个区域内所有的元素都会变成 0。 给定游戏目前的矩阵，小蓝想知道他最多可以进行多少次上述操作。 $T$ 字型区域是指形如 $(x-1,y)→(x,y)→(x+1,y)→(x,y+1)$ 的四个点所形成的区域。其旋转 $90°,180°,270°$ 的形式同样也视作 $T$ 字形区域。

输入格式

输入包含多组数据。

输入的第一行包含一个整数 $D$ 表示数据组数。

对于每组数据，第一行包含一个整数 $n$。

接下来 $n$ 行每行包含 $n$ 个 0 或 1，表示矩阵 $A_{i,j}$ 的每个位置的值。

输出格式

输出 $D$ 行，每行包含一个整数表示小蓝最多可以对当前询问中的矩阵操作的次数。

样例

1
3
001
011
111

5

样例说明

我们用 $X$ 表示某次操作选中的 $T$ 字形，以下给出一种可行方案：

001    XXX    0X0    00X    0X0    X00
011 => 0X1 => XXX => 0XX => XX0 => XX0
111    111    111    11X    1X0    X00

评测用例规模与约定

对于 $10\%$ 的评测用例，$n=3$；

对于 $40\%$ 的评测用例，$n≤30$；

对于所有评测用例，$3≤n≤2000$，矩阵中仅含 0 和 1。