题目描述

Alice 和 Shinobu 在玩一个游戏。现在有 $n$ 个点，点有黑白两种颜色。初始每个点都是孤立的白点，Alice 和 Shinobu 轮流操作，Alice 先手：

• 每轮 Alice 选择一对没有边的点对 $u,v$ 并连无向边 $(u,v)$，不能连自环。
• 每轮 Shinobu 选择一个点并翻转其颜色（黑变白，白变黑）。

当某一次操作后图中存在同色三元环（即存在点 $a,b,c$ 使 $a,b,c$ 同色且 $(a,b),(b,c),(c,a)$ 都已经连上）或者对手无法操作时，操作者获胜。假设两人都绝顶聪明，问谁存在必胜策略？

输入格式

本题有多组询问。

第一行一个正整数 $T$ 表示询问组数。

后 $T$ 行，每行一个正整数 $n$ 表示游戏的点数。

输出格式

$T$ 行，每行一个 Alice 或 Shinobu，表示最后谁会赢。

2
3
6

Shinobu
Alice

1
1000000000

Alice

提示

样例 $1$ 解释：

对于第 $1$ 组数据，Alice 一定在 $3$ 轮后连上 $(1,2),(2,3),(3,1)$，Shinobu 把 $1,2,3$ 依次变黑即可。

对于第 $2$ 组数据，Alice 分 $8$ 轮连上 $(1,2),(2,3),(3,4),(4,5),(5,6),(6,1),(1,4),(2,5)$，然后 Alice 必胜：

• $1,2,4,5$ 中三个同色，连上它们；
• $1,2/4,5$ 同色，将 $6$ 与 $2/4$ 中同色的那个相连；
• $1,4/2,5$ 同色，方案同上；
• $1,5/2,4$ 同色，则 $3/6$ 必然同色（颜色换了 $8$ 次，黑点必有偶数个），即 $2,3,4/5,6,1$ 必然同色，连上即可。

本题采用捆绑测试。

• Subtask 1 (10pts)：$n\le 6$。
• Subtask 2 (40pts)：$n\ge 10^7$。
• Subtask 3 (50pts)：无特殊限制。

对于全部数据，$1\le T\le 10^6$，$1\le n\le 10^9$。