Problem Statement

Takahashi and Aoki will play the following game.

1. For each $i=1,2,\ldots,N$ in this order, do the following.

• Write each integer from $l_i$ through $r_i$ once on the blackboard. (Here, $l_i$ and $r_i$ are non-negative integers from the input.)

2. While one or more integers are written on the blackboard, the players take turns doing the following, with Takahashi going first.

• Choose and perform exactly one of the following two operations.
  • Delete all even numbers written on the blackboard, and replace each remaining integer with half its value rounded down to an integer.
    • Delete all odd numbers written on the blackboard, and replace each remaining integer with half its value.

3. When no integer is written on the blackboard, the game ends and the last player to perform an operation wins.

It can be proved that the game ends in a finite number of operations if Takahashi and Aoki act optimally. Find the winner in this case.

Solve the above problem for $T$ cases.

Constraints

• $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}$
• The sum of $N$ over the test cases in a single input is at most $10^4$.
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{test}_i$ represents the $i$-th test case:

T
\mathrm{test}_1
\vdots
\mathrm{test}_T

Each test case is given in the following format:

N
l_1 r_1
\vdots
l_N r_N

Output

Print $T$ lines. The $i$-th line should contain Takahashi if Takahashi wins in the $i$-th test case, and Aoki if Aoki wins.