题目描述

对于两个非负整数 $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。

样例 1

输入

4
2 3 4 6

输出

Takahashi
Aoki
Takahashi
Aoki

样例 2

输入

4
2 155 155 155

输出

Takahashi
Takahashi
Takahashi
Takahashi

样例 3

输入

20
2579 25823 32197 55685 73127 73393 74033 95252 104289 114619 139903 144912 147663 149390 155806 169494 175264 181477 189686 196663

输出

Takahashi
Aoki
Takahashi
Aoki
Takahashi
Takahashi
Takahashi
Takahashi
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi

说明/提示

限制条件

• $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 翻译