题目描述

高桥君和青木君正在玩取石子游戏。一开始有 $N$ 个石堆，第 $i$ 个石堆中有 $A_i$ 个石子，并且有一个整数 $K_i$。

高桥君和青木君轮流进行如下操作，高桥君先手：

• 选择一个石堆。如果选择了第 $i$ 个石堆，且该堆还剩 $X$ 个石子，则可以从中取走任意数量的石子，数量不少于 $1$ 个且不超过 $floor(X/K_i)$ 个。

无法进行操作的一方判负。请判断在双方都采取最优策略的情况下，谁会获胜。如果高桥君获胜，输出 Takahashi，否则输出 Aoki。

其中，$floor(x)$ 表示不超过 $x$ 的最大整数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $K_1$ $:$ $A_N$ $K_N$

输出格式

如果高桥君获胜，输出 Takahashi；如果青木君获胜，输出 Aoki。

样例 1

输入

2
5 2
3 3

输出

Aoki

样例 2

输入

3
3 2
4 3
5 1

输出

Takahashi

样例 3

输入

3
28 3
16 4
19 2

输出

Aoki

样例 4

输入

4
3141 59
26535 897
93 23
8462 64

输出

Takahashi

说明/提示

限制条件

• $1 \leq N \leq 200$
• $1 \leq A_i, K_i \leq 10^9$
• 输入均为整数

样例解释 1

一开始，第 $1$ 个石堆最多可以一次取走 $floor(5/2)=2$ 个石子，第 $2$ 个石堆最多可以一次取走 $floor(3/3)=1$ 个石子。

• 高桥君如果先从第 $1$ 个石堆取 $2$ 个石子，则第 $1$ 个石堆剩 $3$ 个石子，此时最多可以一次取走 $floor(3/2)=1$ 个石子，第 $2$ 个石堆依然最多可以一次取走 $floor(3/3)=1$ 个石子。
• 接着，青木君从第 $2$ 个石堆取 $1$ 个石子，则第 $2$ 个石堆剩 $2$ 个石子，此时最多可以一次取走 $floor(2/3)=0$ 个石子，即无法再从第 $2$ 个石堆取石子。
• 然后，高桥君从第 $1$ 个石堆取 $1$ 个石子，则第 $1$ 个石堆剩 $2$ 个石子，此时最多可以一次取走 $floor(2/2)=1$ 个石子，第 $2$ 个石堆无法再取石子。
• 最后，青木君从第 $1$ 个石堆取 $1$ 个石子，则第 $1$ 个石堆剩 $1$ 个石子，此时最多可以一次取走 $floor(1/2)=0$ 个石子，第 $2$ 个石堆也无法再取石子。

此时无法再进行操作，因此青木君获胜。即使高桥君采取其他行动，青木君也能通过最优策略获胜。

由 ChatGPT 4.1 翻译