Problem Description

Alice and Shinobu are playing a game. There are $n$ points, each of which can be either black or white. Initially, all points are isolated white points. Alice and Shinobu take turns to make moves, with Alice starting first:
- Each turn, Alice selects a pair of points $u, v$ that are not connected by an edge and connects them with an undirected edge $(u, v)$, without forming a self-loop.
- Each turn, Shinobu selects a point and flips its color (black to white, white to black).

The game ends when, after a move, there exists a monochromatic triangle (i.e., there are points $a, b, c$ such that $a, b, c$ are of the same color and edges $(a, b), (b, c), (c, a)$ are all connected) or when the opponent cannot make a move. The player who makes the winning move is declared the winner. Assuming both players are perfectly strategic, who has the winning strategy?

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$ representing the number of test cases.

The next $T$ lines each contain a positive integer $n$ representing the number of points in the game.

Output Format

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

Sample Input and Output

Sample Input #1

2
3
6

Sample Output #1

Shinobu
Alice

Sample Input #2

1
1000000000

Sample Output #2

Alice

Notes

Explanation of Sample #1:

For the first set of data, Alice will definitely connect $(1,2), (2,3), (3,1)$ after 3 rounds, and Shinobu can simply flip $1, 2, 3$ to black in sequence.

For the second set of data, Alice will connect $(1,2), (2,3), (3,4), (4,5), (5,6), (6,1), (1,4), (2,5)$ in 8 rounds, and then Alice is guaranteed to win:

• Among $1, 2, 4, 5$, three of them are of the same color, connect them;
• If $1, 2$ or $4, 5$ are of the same color, connect $6$ with the one that is of the same color;
• If $1, 4$ or $2, 5$ are of the same color, the strategy is the same as above;
• If $1, 5$ or $2, 4$ are of the same color, then $3$ or $6$ must be of the same color (since the color has been flipped 8 times, there must be an even number of black points), meaning $2, 3, 4$ or $5, 6, 1$ must be of the same color, connect them accordingly.

This problem is tested in groups.

• Subtask 1 (10pts): $n \le 6$.
• Subtask 2 (40pts): $n \ge 10^7$.
• Subtask 3 (50pts): No additional constraints.

For all data, $1 \le T \le 10^6$, $1 \le n \le 10^9$.

见题面 Input 部分

见题面 Output 部分