Alice has types of coins. The values of the types of coins are , respectively. Each kind of coin has an unlimited supply.

Bob also has types of coins. The values of the types of coins are , respectively. Each kind of coin has an unlimited supply.

There are queries. The -th query is described as an integer number . The answer to the query is the minimum number of coins that is necessary to obtain the value using some subset of coins (Alice or Bob). If it is impossible to obtain the value, the answer to the -th query is . If both of them can obtain the minimum number, output "both". In the other case, you should output either "A" if Alice can obtain the minimum number or "B" if Bob can obtain the minimum number. 

The first line of the input contains an integer  () --- the number of queries.

Each of the following  lines contains an integer  (), the value obtained.

For each query, print a single line according to the description above.

4
0
1
2
3

both
-1
A
A