P10152 "LAOI-5" Jigsaw Puzzle.

Alice and Shinobu are playing a game. There are $n$ vertices, and each vertex is either black or white. Initially, every vertex is an isolated white vertex. Alice and Shinobu take turns to operate, and Alice moves first: - In each round, Alice chooses a pair of vertices $u,v$ with no edge between them and adds an undirected edge $(u,v)$. Self-loops are not allowed. - In each round, Shinobu chooses one vertex and flips its color (black becomes white, white becomes black). If, after some operation, there exists a monochromatic triangle in the graph (that is, there exist vertices $a,b,c$ such that $a,b,c$ have the same color and $(a,b),(b,c),(c,a)$ have all been added), or the opponent has no valid move, then the player who just operated wins. Assuming both players are perfectly smart, determine who has a winning strategy.

**This problem has multiple queries.** The first line contains a positive integer $T$, the number of queries. The next $T$ lines each contain a positive integer $n$, the number of vertices in the game.

Output $T$ lines, each containing `Alice` or `Shinobu`, indicating who will win in the end.

Explanation of Sample $1$: For the $1$-st test case, Alice will surely add $(1,2),(2,3),(3,1)$ after $3$ rounds. Shinobu can make $1,2,3$ black one by one. For the $2$-nd test case, Alice adds $(1,2),(2,3),(3,4),(4,5),(5,6),(6,1),(1,4),(2,5)$ in $8$ rounds, and then Alice will surely win: - Among $1,2,4,5$, three vertices have the same color, so connect those three. - $1,2/4,5$ have the same color, so connect $6$ to the one in $2/4$ that has the same color. - $1,4/2,5$ have the same color, do the same as above. - If $1,5/2,4$ have the same color, then $3/6$ must have the same color (the color has been flipped $8$ times, so the number of black vertices must be even). Therefore, $2,3,4/5,6,1$ must be the same color, so just connect them. ---------- **This problem uses bundled tests.** - Subtask 1 (10pts): $n\le 6$. - Subtask 2 (40pts): $n\ge 10^7$. - Subtask 3 (50pts): no special restrictions. For all testdata, $1\le T\le 10^6$, $1\le n\le 10^9$. Translated by ChatGPT 5