题目描述

对于两个非负整数$x$和$y$，$\\gcd(x,y)$ 表示$x$和$y$的最大公约数（当$x=0$时，$\\gcd(x,y)=\\gcd(y,x)=y$）。

黑板上有 $N$ 个整数，第 $i$ 个整数为 $A_i$。这 $N$ 个整数的最大公约数是 $1$。

高桥和青木将互相进行游戏。在将一个整数 $G$ 初始化为 $0$ 后，他们轮流执行以下操作，高桥先开始。

• 选择黑板上的一个数 $a$，使得 $\\gcd(G,a)\\neq 1$，擦除它，并用 $\\gcd(G,a)$ 替换 $G$。

首先无法进行操作的一方输掉游戏。

对于每个 $i\\ (1\\leq i \\leq N)$，确定高桥在他的第一回合中选择黑板上的第 $i$ 个整数后，双方都采取最优策略时的获胜者。

约束条件

• $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$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $\\dots$ $A_N$

输出

打印 $N$ 行。第 $i$ 行应包含获胜者的名字，Takahashi 或 Aoki，表示高桥在他的第一个回合中选择黑板上的第 $i$ 个整数后，双方都采取最优策略时的结果。

示例输入1

4
2 3 4 6

示例输出1

Takahashi
Aoki
Takahashi
Aoki

例如，当高桥在他的第一个回合中选择第四个整数 $A_4=6$ 时，青木可以选择第二个整数 $A_2=3$，使得 $G=3$。现在，高桥无法再进行选择，所以青木获胜。因此，第四行应包含 Aoki。

示例输入2

4
2 155 155 155

示例输出2

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

示例输出3

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