問題文

高橋君と青木君が以下のような二人ゲームで勝負する。

まず、正の整数 N が与えられる。 また、変数 x を 1 に初期化する。高橋君から始め、高橋君と青木君が交互に次の操作を行う。

• x の値を 2x または 2x+1 に置き換える。

x が N よりも大きくなったとき、最後に操作を行った人が負けである。

二人が最善を尽くすとき、どちらが勝つか求めよ。

入力例1

1

出力例1

Aoki

高橋君がどのように操作を行っても x>1 となってしまう。

入力例2

5

出力例2

Takahashi

高橋君が x=3 とすると、青木君がどのように操作を行っても x>5 となってしまう。

入力例3

7

出力例3

Aoki

入力例4

10

出力例4

Takahashi

入力例5

123456789123456789

出力例5

Aoki

N は 32 bit 整数型に収まらない。