[ARC091F] Strange Nim

有 $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$

[problemUrl]: https://atcoder.jp/contests/arc091/tasks/arc091_d 高橋君と青木君は、石取りゲームをしています。最初、山が $ 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` を出力せよ。

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 $ 個目の山からは石を取り除くことはできません。 これ以上の操作はできないため、青木君の勝ちです。高橋君がそれ以外の行動をした場合も、青木君はうまく行動を選ぶことで勝つことができます。