终局预测

题目描述

井字棋是伞伞最爱的游戏！

棋盘是一个 $3×3$ 的格子，两位玩家轮流在上面放棋子：一位用 X，一位用 O。谁先在横、竖或对角线上连成 三个 自己的棋子，谁就获胜！如果棋盘下满了还没有人赢，那就是平局。

现在，伞伞看到了一个还没下完的棋盘，并且知道这局游戏一开始是谁先下的（也就是"先手"）。他想知道：在不考虑任何下棋策略（也就是双方都随便下，把每种可能的下法都算上）的情况下，最终先手获胜、平局 或 先手失败 的结局各有多少种？

对于任意两种结局，只要某一轮某一个人放棋子的位置不同，则两种结局视为不同，即使最终的盘面可能完全相同。

输入格式

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

对于每组数据：

• 第一行一个字符串 $f$，值为 X 或 O，表示在这一局中先手是谁。
• 接下来三行，每行一个长度为 $3$ 的字符串，组成一个 $3×3$ 的棋盘。棋盘上包含 X、O 和 .（点表示空格）。

输出格式

对于每组数据，输出一行三个整数，依次表示先手获胜、平局、先手失败的结局数量。

样例

2
X
XOX
O..
X.O
O
...
.O.
X..

3 2 0
1830 576 792

数据规模与约定

下发文件

下发文件对应子任务 $1,2,3$。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 10^{2},f \in \{X,O\},s_{i,j} \in \{X,O,.\}$ $(1 \leq i,j \leq 3)$。保证给定的所有初始盘面，游戏均未结束。