「LAOI-5」拼图

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$。