P14017 [ICPC 2024 Nanjing R] 棋字井

Alice 和 Bob 正在 $n$ 块 $3$ 行 $3$ 列的棋盘上玩 “棋字井” 游戏。一些棋盘的一些格子一开始是空的，而其它格子里都有一些记号。Alice 先行动，他们轮流选择一个棋盘，并在该棋盘的一个空格中画上自己的记号。Alice 的记号是 `x`，Bob 的记号是 `o`。 每位玩家必须确保在他/她行动之后，任何棋盘的任何行、列或对角线上都没有三个相同的标记。无法在自己回合进行有效行动的玩家将输掉游戏，同时宣告另一位玩家获胜。 给定 $n$ 块棋盘的初始状态，假设两位玩家都采用最优策略，您需要确定谁会获胜。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示游戏中的棋盘数量。 接下来输入 $n$ 块大小为 $3 \times 3$ 的棋盘。对于每块棋盘： - 如果不是第一块棋盘，首先会有一个空行。 - 对于接下来三行，第 $i$ 行输入一个长度为 $3$ 的字符串 $s_{i,1}s_{i,2}s_{i,3}$，字符串由字符 `x`，`o` 和 `.` 组成，描述一块大小为 $3 \times 3$ 的棋盘。令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子。若 $s_{i, j} =$ `x` 则格子 $(i, j)$ 里有记号 `x`；若 $s_{i, j} =$ `o` 则格子 $(i, j)$ 里有记号 `o`；若 $s_{i, j} =$ `.` 则格子 $(i, j)$ 是空的。 保证任何棋盘的任何行、列或对角线上都没有三个相同的标记。另外保证所有数据 $n$ 之和不超过 $10^5$。

每组数据输出一行。如果 Alice 获胜，则输出 $\texttt{Alice}$；如果 Bob 获胜，则输出 $\texttt{Bob}$。