Migrated from Lutece 2599 井字棋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

瓜皮大哥和 $Namelessoier$ 今天真的很无聊，他们想玩井字棋游戏。

规则与一般井字棋基本相同。 两名玩家瓜皮大哥和 $Namelessoier$ 轮流在 3 x 3 棋盘上玩。 瓜皮大哥先走。 目标是在某行、某列或某条对角线上将自己的棋子填满，形成连续的连接。

在我们的问题中，规则有些不同。 即使一名玩家达到了行（或列或对角线）连接，游戏仍将继续，直到所有九个位置都放置。 最后，我们将瓜皮大哥的连接数减去 $Namelessoier$ 的连接数作为游戏的最终得分。 瓜皮大哥想要最大化总分，而 $Namelessoier$ 想要最小化它。

由于某种神秘的力量，棋盘上已经有了一些棋子。 瓜皮大哥和 $Namelessoier$ 希望你帮助计算从给定情况开始的最终分数。

显然你知道这两个人都是绝对聪明的，所以他们走出的每一步都是最优的。

Input

输入的第一行包含一个整数 $T (1 \le T \le 40000)$ ，表示测试用例的数量。

对于每个测试用例，第一行是一个整数 $0$ 或 $1$，其中 $1$ 表示轮到瓜皮大哥上场，$0$ 表示轮到 $Namelessoier$ 上场。

在接下来的三行中，每行包含代表棋盘情况的 $3$ 字符：

• '$.$'表示空缺位置；
• '$O$'表示瓜皮大哥的棋子已被放置；
• '$X$'表示 $Namelessoier$ 的棋子已放置。

Output

输出 $T$ 行。

对于每个测试用例，输出一行包含一个整数，以表示从给定情况开始的最终分数。

Samples

2
1
.XX
O.X
XOX
0
OOO
OOO
OOO

-2
8

Resources

2022 UESTC ICPC Training for String and Search Algorithm