A72030 | 桌面游戏

样例1解释

• 第一组数据中，只有一个空位，剩余数字为 9，先手只能将 9 填入右下角。此时 Dr. X 的分数为 1 \times 2 \times 3 + 4 \times 5 \times 6 + 7 \times 8 \times 9 = 630，Dr. Y 的分数为 1 \times 4 \times 7 + 2 \times 5 \times 8 + 3 \times 6 \times 9 = 270，因此先手获胜。
• 第二组数据中，只有一个空位，剩余数字同样为 9。先手填入后，Dr. X 的分数为 270，Dr. Y 的分数为 630，因此后手获胜。
• 第三组数据中，剩余数字为 3 和 9。先手必须先填入 3，后手再填入 9。无论先手如何选择位置，后手都能使自己的最终分数更高，因此后手必胜。

样例2解释

• 这一组的剩余数字为 1、2、8。先手若不把 1 填在左上角，后手就能获胜，因此先手的最优选择是先填左上角。之后后手把 2 填在第三行第二列，先手再把 8 填在第一行第二列，最终方格为：

1 8 3 4 5 6 7 2 9

此时 Dr. X 的分数为 1 \times 8 \times 3 + 4 \times 5 \times 6 + 7 \times 2 \times 9 = 270，Dr. Y 的分数为 1 \times 4 \times 7 + 8 \times 5 \times 2 + 3 \times 6 \times 9 = 270，因此平局。

数据规模

• 对于 30\% 的数据，空位 0 的个数不超过 2。
• 对于 60\% 的数据，空位 0 的个数不超过 5。
• 对于 100\% 的数据，空位 0 的个数不超过 9，1 \leq T \leq 20。