题目描述

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

输入 #1

4
2 3 4 6

输出 #1

Takahashi
Aoki
Takahashi
Aoki

输入输出样例 #2

输入 #2

4
2 155 155 155

输出 #2

Takahashi
Takahashi
Takahashi
Takahashi

输入输出样例 #3

输入 #3

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

输出 #3

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

黑板上可能会有多个相同的整数。