AT_agc064_c [AGC064C] Erase and Divide Game

[problemUrl]: https://atcoder.jp/contests/agc064/tasks/agc064_c 高橋君と青木君が以下のようなゲームをします。 1. $ i=1,2,\ldots,N $ の順に次の操作をする。 - $ l_i $ 以上 $ r_i $ 以下の整数を $ 1 $ 個ずつ黒板に書く。(ここで、$ l_i,r_i $ は入力より与えられる非負整数である) 2. 黒板に整数が $ 1 $ 個以上書かれている間、高橋君を先手として交互に次の操作をする。 - 以下の $ 2 $ 種類の操作のうちちょうど一方を選び、実行する。 - 黒板に書かれている偶数をすべて削除し、残った整数をそれぞれ $ 2 $ で割って小数点以下を切り捨てた値に書き換える。 - 黒板に書かれている奇数をすべて削除し、残った整数をそれぞれ $ 2 $ で割った値に書き換える。 3. 黒板に整数が $ 1 $ 個も書かれていない状態になった場合、最後に操作をした人を勝者としてゲームを終了する。 高橋君と青木君が最適な行動を取った場合、ゲームは有限回の操作で終了することが示せます。この時の勝者を求めてください。 $ 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\ \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} $ - $ 1 $ つの入力に含まれるテストケースについて、$ N $ の総和は $ 10^4 $ 以下 - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のテストケースに対するゲームの流れの例を以下に示します。 - 黒板に $ 1,2,5,6,7 $ が $ 1 $ 個ずつ書かれる。 - 高橋君が奇数を削除する方の操作をする。黒板から $ 1,5,7 $ が削除され、残った整数 $ 2,6 $ がそれぞれ $ 2 $ で割った値の $ 1,3 $ に書き換えられる。 - 青木君が奇数を削除する方の操作をする。黒板から $ 1,3 $ が削除され、黒板に整数が $ 1 $ 個も書かれていない状態になったため最後に操作をした青木君を勝者としてゲームが終了する。