H. The Game of Two Elves

Grandpa Frost has devised an intriguing game for his elf friends, Archie and Anton. He has drawn a sequence of $n$ bits for them to play with.

The game proceeds in turns, starting with Archie. During a turn, an elf must select an index $i$ such that $1\le i\le n$ and the $i$-th bit of the sequence is $1$. The elf then flips all bits from position $1$ to $i$ (i.e., bits that are $0$ become $1$, and bits that are $1$ become $0$). The elf who cannot make a move loses the game.

Both Archie and Anton are very clever and will play the game optimally. Your task is to determine the winner for each of the $t$ initial sequences provided by Grandpa. Note that all $t$ games are independent of each other.

Input

The first line contains a single integer $t$ ($1\le t\le 50$), representing the number of games.

Each game is described by two lines:

The first line contains a single integer $n$ ($1\le n\le 10^4$), the length of the bit sequence.

The second line contains a sequence of $n$ bits.

Output

For each game, output "Archie" if Archie wins, or "Anton" if Anton wins.

Examples

Note

In the first example, after Archie's only possible move, the sequence becomes "110". Anton can then change it to "000" in one move and win.

In the second and third examples, Archie wins after making just one move.

Scoring

This problem includes two test cases with non-zero scores. One test case is worth $25$ points and has additional constraints: $t=16$, $n=4$.