题目描述

小蓝正在玩一款游戏，游戏中有一个 $n \times 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 \leq 30$；
• 对于所有评测用例，$3 \leq n \leq 2000$，矩阵中仅含 $0$ 和 $1$。此外，$1 \leq D \leq 100$，单个测试点内的 $n$ 之和（即 $\sum n$）不超过 $5000$。