小藍正在玩一款游戲，游戲中有一個n × n大小的 01 矩陣 A_{i, j} 。

小藍每次需要選擇一個T字型的區(qū)域，且這個區(qū)域內(nèi)至少要有一個 1 。選中后，這個區(qū)域內(nèi)所有的元素都會變成 0。

給定游戲目前的矩陣，小藍想知道他最多可以進行多少次上述操作。 

T字型區(qū)域是指形如 (x ? 1, y) (x, y) (x + 1, y) (x, y + 1) 的四個點所形成的區(qū) 域。其旋轉(zhuǎn) 90, 180, 270 度的形式同樣也視作 T 字形區(qū)域。 

輸入包含多組數(shù)據(jù)。

輸入的第一行包含一個整數(shù) D 表示數(shù)據(jù)組數(shù)。

對于每組數(shù)據(jù)，第一行包含一個整數(shù)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 。