AT_arc155_d [ARC155D] Avoid Coprime Game

对于两个非负整数 $x, y$，$\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公约数（其中，当 $x=0$ 时，$\gcd(x, y)=\gcd(y, x)=y$）。 黑板上写有 $N$ 个整数，第 $i$ 个整数为 $A_i$。这 $N$ 个整数的最大公约数为 $1$。 高桥君和青木君进行一场对战游戏。初始时整数 $G=0$，两人轮流操作，高桥君先手。每次操作如下： - 从黑板上选择一个满足 $\gcd(G, a) \neq 1$ 的数 $a$，将其擦去，并用 $\gcd(G, a)$ 替换 $G$。 无法进行操作的一方判负。 对于每个 $i\ (1\leq i \leq N)$，请判断如果高桥君在第一回合选择第 $i$ 个整数，之后双方都采取最优策略，最终谁会获胜。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出 $N$ 行。第 $i$ 行输出高桥君在第一回合选择第 $i$ 个整数后，双方都采取最优策略时的胜者。如果高桥君获胜，输出 `Takahashi`；如果青木君获胜，输出 `Aoki`。

### 限制条件 - $2 \leq N \leq 2 \times 10^5$ - $2 \leq A_i \leq 2 \times 10^5$ - $N$ 个整数 $A_i\ (1\leq i \leq N)$ 的最大公约数为 $1$ - 输入均为整数 ### 样例解释 1 例如，如果高桥君在第一回合选择第 $4$ 个整数 $A_4=6$，青木君可以选择第 $2$ 个整数 $A_2=3$，此时 $G=3$。之后高桥君无法再选择任何整数，因此青木君获胜。所以第 $4$ 行应输出 `Aoki`。 ### 样例解释 2 黑板上可能会有多个相同的整数。 由 ChatGPT 4.1 翻译