题目描述

注意：本题中黑白棋规则和一般规则有不同，请仔细读题

本题中黑白棋规则如下：

• 棋盘大小为 $n \times n$
• 初始棋盘为空
• 黑白两方轮流下棋，黑方先手
• 每次选择一个空格落子
• 落子后，观察该棋子正上、正下、正左、正右、左上、右上、左下、右下 $8$ 个方向，找到每个方向最近的一枚同色棋子（如果没有，则该方向不做操作），如果该棋子与本次落子的棋子之间仅包含对方的棋子而没有空格，则这些对方的棋子全部变换颜色为本方棋子
• 棋盘全满时结束，统计双方棋子数，多者获胜，相等则为平局

请注意：

• 一次落子后，$8$ 个方向满足颜色变换条件的棋子会同时变色
• 即使本次选择落子的位置无法使对方任何一个棋子变色，依然可以在这里落子，故只要棋盘上有空格存在，就有位置可以落子，也就必须选择一处落子

现给出下棋中途的局面，保证还有空格，请判断即将落子的人是哪一方，并决定它的落子位置，目标是使本次落子后，完成棋子颜色的变换后，本方棋子数与对方棋子数之差（本方棋子数量 - 对方棋子数量）最大，请输出这个差值

输入格式

本题每个测试点包含多组测试数据

第一行，一个正整数 $T$，表示数据组数

对于每组数据

• 第一行，一个正整数 $n$，表示棋盘大小
• 接下来 $n$ 行，每行 $n$ 个字符，表示棋盘情况，其中 o 表示白棋，x 表示黑棋，. 表示空格

输出格式

$T$ 行，每行一个整数，表示每组数据的答案

样例

样例输入1

3
4
....
.xo.
.ox.
....
4
..x.
.xx.
.ox.
....
4
....
xxx.
....
....

样例输出1

3
0
-2

样例解释

对于第 $1$ 组数据，一种最优局面为：

..x.
.xx.
.ox.
....

对于第 $2$ 组数据，一种最优局面为：

..x.
.xx.
.ooo
....

对于第 $3$ 组数据，一种最优局面为：

....
xxxo
....
....

数据范围

对于 $100\%$ 的数据，$1 \leq T \leq 20, 1 \leq n \leq 100$