The scientific committee of JBOI 2016 together with the competitors is placed in the ethno complex Macedonian Village. The contestants found the tasks in the first competition day very hard, so they are organizing to hack the tasks for the second competition day. Are you ready to be a spy?

The scientific committee consists of N members (with IDs numbered from 1 to N), placed somewhere in the Macedonian Village. Unfortunately, we don't know exactly where they are. What we do know - each member has different position. In fact the position of the i-th member could be expressed as (x_i, y_i). Each member has exactly one reporter, also a member, to whom he should send a message. A reporter is chosen according to one of two used connectivity systems: Armadillo or Benedictus.

According to Armadillo, the reporter of the i-th member is the member most distant to him (according to standard metrics: Euclidean distance where the distance between two points (x₁, y₁) and (x₂, y₂) is defined as (x₁ - x₂)² + (y₁ - y₂)²).

According to Benedictus, the reporter of the i-th member becomes the member which has the lowest y-coordinate that is strictly bigger than y_i. If such member doesn't exist then the member with the lowest y coordinate is chosen.

It's easy to note, that these systems aren't complete and there can be conflicts. Because of that, the Chairman decided that when according to the used system the reporter can't be chosen uniquely, for Armadillo the member with the lowest ID among them will be chosen and for Benedictus the member with the lowest x-coordinate among them.

It's everything we know so far. Now it's your turn. We've come across a list of reporters of each of the members. We can't distinguish whether the scientific committee uses Armadillo or Benedictus. Will you manage?

Input

Because there are just two possible connectivity systems, to prevent contestants from earning points by randomly printing the result, each input will consists of a number of situations.

line 1: M, the number of situations to consider
next M lines: first N, the number of members in the scientific committee, and then N integers r₁,r₂, r₃,...,r_N, where r_i is the ID of the reporter of the i^th member.

Subtasks

(10 points) 1 ≤ M ≤ 20, 2 ≤ N ≤ 20
(15 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 1000, There is no BOTH in the solution.
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000, There is no BOTH in the solution.
(15 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000, The positions of all members are points that form a regular n-sided polygon
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 1000
(20 points) 1 ≤ M ≤ 10, 2 ≤ N ≤ 100000

Output

M lines: For each situation in each line you need to print “A” if only Armadillo strategy can be used, “B” if only Benedictus strategy can be used or “BOTH” if both strategies can be used.

Constraints

Time limit: 1500 milliseconds
Memory limit: 64 megabytes

Examples

input
3
3 2 3 1
4 2 1 4 3
2 2 1

output
B
A
BOTH

Explanation: There are 3 situations to consider (M=3).

For the first list of reporters, the scientific committee could only use Benedictus. Example positions of the committee members with ID numbers 1, 2 and 3 are: (0, 0), (0, 1) and (0, 2), accordingly.

For the second list of reporters, Armadillo is only possible strategy and example positions of the committee members with ID numbers 1, 2, 3 and 4 are: (0, 0), (1, 1), (1, 0), (0, 1).

For the third sample test we can't uniquely determine the system. If the coordinates of the member with ID=1 is (0, 0), and the coordinates of the member with ID=2 is (1, 1), both answers are correct. Therefore, we print BOTH.