题目描述

高桥君和青木君进行如下游戏。

1. 按照 $i=1,2,\ldots,N$ 的顺序，进行以下操作：
   • 在黑板上依次写下 $l_i$ 到 $r_i$ 之间的每一个整数（$l_i,r_i$ 是输入给定的非负整数）。
2. 只要黑板上还有至少一个整数，高桥君先手，轮流进行以下操作：
   • 从以下两种操作中恰好选择一种并执行：
     • 删除黑板上所有偶数，并将剩下的每个整数都替换为其除以 $2$ 并向下取整的值。
     • 删除黑板上所有奇数，并将剩下的每个整数都替换为其除以 $2$ 的值。
3. 当黑板上没有任何整数时，最后进行操作的人获胜，游戏结束。

已知高桥君和青木君都会采取最优策略，可以证明游戏一定会在有限步内结束。请你求出每组数据中谁会获胜。

请你针对 $T$ 组数据，回答上述问题。

输入格式

输入按以下格式从标准输入读入。这里，$\mathrm{test}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{test}_1$
$\vdots$
$\mathrm{test}_T$

每个测试用例格式如下：

$N$
$l_1$ $r_1$
$\vdots$
$l_N$ $r_N$

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的胜者，高桥君获胜则输出 Takahashi，青木君获胜则输出 Aoki。

样例 1

输入

3
2
1 2
5 7
1
0 100
10
1312150450968413 28316250877914571
74859962623690078 84324828731963974
148049062628894320 252509054433933439
269587449430302150 335408917861648766
349993004923078531 354979173822804781
522842184971407769 578223540024979436
585335723211047194 615812229161735895
645762258982631926 760713016476190622
779547116602436424 819875141880895723
822981260158260519 919845426262703496

输出

Aoki
Aoki
Takahashi

说明/提示

限制条件

• $1 \leq T \leq 10^4$
• $1 \leq N \leq 10^4$
• $0 \leq l_i \leq r_i \leq 10^{18}$
• $r_i < l_{i+1}$
• 所有测试用例中 $N$ 的总和不超过 $10^4$
• 输入均为整数

样例解释 1

下面给出第 $1$ 个测试用例的游戏流程示例：

• 黑板上依次写下 $1,2,5,6,7$。
• 高桥君选择删除奇数。黑板上 $1,5,7$ 被删除，剩下的 $2,6$ 分别变为 $1,3$。
• 青木君选择删除奇数。黑板上 $1,3$ 被删除，黑板上已无整数，因此最后操作的青木君获胜，游戏结束。

由 ChatGPT 4.1 翻译