题目描述

高橋君と青木君は、石取りゲームをしています。最初、山が $N$ 個あり、$i$ 個目の山には $A_i$ 個の石があり、整数 $K_i$ が定まっています。

高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。

• 山を $1$ つ選ぶ。$i$ 個目の山を選び、その山に $X$ 個の石が残っている場合、$1$ 個以上 $floor(X/K_i)$ 個以下の任意の個数の石を $i$ 個目の山から取り除く。

先に操作ができなくなったプレイヤーが負けです。両者最善を尽くしたとき、どちらのプレイヤーが勝つか判定してください。 ただし、$floor(x)$ で $x$ 以下の最大の整数を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君が勝つなら Takahashi を、青木君が勝つなら Aoki を出力せよ。

题目大意

有 $n$ 堆石子，每堆有 $a_i$ 个石子和一个常数 $k_i$，两人轮流操作，每次可以从任意一堆（假设为第 $i$ 堆）石子中取出至少一个至多 $\lfloor\frac{a_i}{k_i}\rfloor$ 个。不能操作者输。先手胜则输出Takahashi，否则输出Aoki。

$n\le 200$，$a_i,k_i\le 10^9$

2
5 2
3 3

Aoki

3
3 2
4 3
5 1

Takahashi

3
28 3
16 4
19 2

Aoki

4
3141 59
26535 897
93 23
8462 64

Takahashi

提示

制約

• $1\ \leq\ N\ \leq\ 200$
• $1\ \leq\ A_i,K_i\ \leq\ 10^9$
• 入力はすべて整数である

Sample Explanation 1

最初、$1$ 個目の山からは $floor(5/2)=2$ 個まで、$2$ 個目の山からは $floor(3/3)=1$ 個までの石を一度に取り除くことができます。 - 高橋君が最初に $1$ 個目の山から $2$ 個の石を取ると、$1$ 個目の山からは $floor(3/2)=1$ 個まで、$2$ 個目の山からは $floor(3/3)=1$ 個までの石を一度に取り除くことができるようになります。 - 次に、青木君が $2$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(3/2)=1$ 個までの石を取り除くことができ、$2$ 個目の山からは ($floor(2/3)=0$ より) 石を取り除くことができなくなります。 - 次に、高橋君が $1$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(2/2)=1$ 個までの石を一度に取り除くことができるようになります。$2$ 個目の山からは石を取り除くことはできません。 - 次に、青木君が $1$ 個目の山から $1$ 個の石を取ると、$1$ 個目の山からは $floor(1/2)=0$ 個までの石を一度に取り除くことができるようになります。$2$ 個目の山からは石を取り除くことはできません。 これ以上の操作はできないため、青木君の勝ちです。高橋君がそれ以外の行動をした場合も、青木君はうまく行動を選ぶことで勝つことができます。