Don't Split The Atom!

Interview

Time limit2sMemory limit512 MB

Summary

Two players alternately split a pile of atoms, and whoever is forced to split a single atom loses; decide the winner for each n.

Level: Medium4 of 10
Topics: Game theory, Math, Greedy, Implementation
Solved: No attempts yet

Problem

Two mad (and evil) scientists, Professor Zoom and Doctor Horrible, have just obtained $n$ atoms of a very rare element, and they want to share them. They have decided to play the following game.

First, Professor Zoom divides the atoms into two non-empty groups. Next, Doctor Horrible takes one group for his evil purposes and splits the other group into two non-empty parts. Then Professor Zoom takes one of the parts and splits the other part into two, returning it to Doctor Horrible. The game continues this way: on every turn, one scientist takes one part and splits the other. Eventually one player is forced to split a single atom. This causes an explosion, and the unlucky splitter loses the game (probably along with his life).

Given the number of atoms $n$ , determine which of the two villains survives the game.

Input

The first line of input contains the number of test cases $z$ ( $1 \leq z \leq 50$ ). The descriptions of the test cases follow.

Every test case consists of one integer $n$ ( $1 \leq n \leq 1\,000\,000$ ), the initial number of atoms.

Output

For each test case output a line containing a single character: 'A' if Professor Zoom wins the game, 'B' if Doctor Horrible wins.

Examples1

Example 1
Input
```
2
2
17
```
Expected output
```
A
B
```