Problem Description

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.

Input Format

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 Format

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

2
3
6

Shinobu
Alice

1
1000000000

Alice

Hint

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