Strange Nim

Takahashi and Aoki are playing a stone-taking game. Initially, there are N piles of stones, and the i-th pile contains A_i stones and has an associated integer K_i.

Starting from Takahashi, Takahashi and Aoki take alternate turns to perform the following operation:

• Choose a pile. If the i-th pile is selected and there are X stones left in the pile, remove some number of stones between 1 and floor(X/K_i) (inclusive) from the pile.

The player who first becomes unable to perform the operation loses the game. Assuming that both players play optimally, determine the winner of the game. Here, floor(x) represents the largest integer not greater than x.

Constraints

• 1 \leq N \leq 200
• 1 \leq A_i,K_i \leq 10^9
• All input values are integers.

Input

Input is given from Standard Input in the following format:

N A_1 K_1 : A_N K_N

Output

If Takahashi will win, print Takahashi; if Aoki will win, print Aoki.

Examples

Input

2 5 2 3 3

Output

Aoki

Input

3 3 2 4 3 5 1

Output

Takahashi

Input

3 28 3 16 4 19 2

Output

Aoki

Input

4 3141 59 26535 897 93 23 8462 64

Output

Takahashi

inputFormat

input values are integers.

Input

Input is given from Standard Input in the following format:

N A_1 K_1 : A_N K_N

outputFormat

Output

If Takahashi will win, print Takahashi; if Aoki will win, print Aoki.

Examples

Input

2 5 2 3 3

Output

Aoki

Input

3 3 2 4 3 5 1

Output

Takahashi

Input

3 28 3 16 4 19 2

Output

Aoki

Input

4 3141 59 26535 897 93 23 8462 64

Output

Takahashi

样例

4
3141 59
26535 897
93 23
8462 64

Takahashi