Problem Description

Alice and Bob are playing a game. They take turns and Alice moves first. There is a set of positive integers. In one's turn, he or she can choose a number (suppose $x$) in the set, and choose a positive integer $k$ ($k$ does not need to be in the set), and replace $x$ with $x-(10^k-1)$. For example, you can make a number $x$ in the set become $x-9$ or $x-99$ or $x-999$ or $x-999\cdots$. After that the set must still be a set of positive integers. That is to say:


* The number must still be positive: $x-(10^k-1) > 0$.
* A set can not have duplicate elements: $x-(10^k-1)$ can not be equal to any other numbers in the set.

They take turns and Alice moves first. The one who can't move loses the game. Now the question is that who will win the game if they play optimally.

Input

There are multiple test cases.

For each test case, the first line contains a number $N$, denoting the number of numbers in the set.

The second line contains $N$ different positive integers $A_1, A_2, \ldots, A_N$, denoting the numbers in the set.

It's guaranteed that $1\leq A_i \leq 10^9$, and the sum of $N$ of all test cases is not larger than $2 \cdot 10^5$.

Output

For each test case, print ``A'' for Alice or ``B'' for Bob in one line, denoting the winner.

3
1 2 3
3
2 11 20
3
11 12 13
3
10 19 28
2
100 1000

B
B
A
A
A