P14017 [ICPC 2024 Nanjing R] Toe-Tac-Tics

Alice and Bob are playing Toe-Tac-Tics on $n$ boards with $3$ rows and $3$ columns. Some cells on the boards are initially empty, while the others already contain some marks. Alice moves first, and they take turns to select a board and put their marks into an empty cell on that board. Alice's mark is `x` and Bob's mark is `o`. Each player must make sure that no three same marks are in any row, column, or diagonal on any board after his/her move. The player who cannot make a valid move on their turn loses, and the other player wins. Given the initial state of the $n$ boards, you need to determine who wins, assuming both players play optimally for victory.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of boards in the game. Then $n$ boards of size $3 \times 3$ follow. For each board: - There will first be an empty line if it is not the first board. - For the following three lines, the $i$-th line contains a string $s_{i,1}s_{i,2}s_{i,3}$ of length $3$ consisting of characters `x`, `o`, and `.`, describing a board of size $3 \times 3$. Let $(i, j)$ be the cell on the $i$-th row and the $j$-th column. If $s_{i, j} =$ `x` then cell $(i, j)$ contains a mark `x`; if $s_{i, j} =$ `o` then cell $(i, j)$ contains a mark `o`; if $s_{i, j} =$ `.` then cell $(i, j)$ is empty. It is guaranteed that no three same marks are in any row, column, or diagonal on any board. It is also guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.

For each test case, output $\texttt{Alice}$ if Alice wins the game, or $\texttt{Bob}$ if Bob wins the game.