小蓝正在玩一款游戏，游戏中有一个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}的每个位置的值。

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 。