分数: 900 点
问题陈述
高桥和青木将进行以下游戏。
- 对于每个 i=1,2,\ldots,N 按照此顺序,执行以下操作。
- 写入每个整数 l_i 通过 r_i 一次在黑板上。 (这里, l_i 和 r_i 是输入中的非负整数。)
- 当一个或多个整数写在黑板上时,玩家轮流执行以下操作,高桥先行。
- 选择并执行以下两个操作之一。
- 删除黑板上写的所有偶数,并将剩余的每个整数替换为向下舍入为整数的一半。
- 删除黑板上写的所有奇数,并将剩余的每个整数替换为其值的一半。
- 选择并执行以下两个操作之一。
- 当黑板上没有写出整数时,游戏结束,最后执行操作的玩家获胜。
可以证明,如果高桥和青木表现最佳,则游戏会在有限次数的操作中结束。找出本例中的获胜者。
解决上述问题 T 案例。
约束
- 1 \leq T \leq 10^4
- 1 \leq N \leq 10^4
- 0 \leq l_i \leq r_i \leq 10^{18}
- r_i \lt l_{i+1}
- 总和 N 单个输入中的测试用例最多 10^4.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{test}_i 代表 i-第一个测试用例:
T
\mathrm{test}_1
\vdots
\mathrm{test}_T
每个测试用例均按以下格式给出:
N l_1 r_1 \vdots l_N r_N
输出
打印 T 行。的 i- 第行应包含 Takahashi 如果高桥在比赛中获胜 i第一个测试用例,以及 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
示例输出 1
Aoki Aoki Takahashi
以下是第一个测试用例的游戏情况示例。 黑板上写了一次
- 每个 1,2,5,6,7 。
- 高桥选择删除奇数。 1,5,7 从黑板上删除,剩下的整数 2,6 被替换为其值的一半,即 1,3。
- 青木选择删除奇数。 1,3 从黑板上被删除,并且黑板上不再写任何整数,因此游戏结束,执行最后一个操作的青木获胜。