D. Differencing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a set $$$P$$$ of the smallest $$$n$$$ primes $$$p_1 = 2 \le p_2 = 3\le \cdots \le p_n$$$. Partition the primes into two subsets $$$A$$$ and $$$B$$$ (which can be empty), such that the difference between the sums of two subsets is minimized.

Example

If $$$N = 9$$$, the set $$$P$$$ is $$$\{2, 3, 5, 7, 11, 13, 17, 19, 23\}$$$. The table below demonstrates an optimal solution:

$$$p_1$$$$$$p_2$$$$$$p_3$$$$$$p_4$$$$$$p_5$$$$$$p_6$$$$$$p_7$$$$$$p_8$$$$$$p_9$$$sum
A257171950
B311132350
Input

Each test contains multiple test cases. The first line contains a single integer $$$T$$$ — the number of test cases. The description of the test cases follows.

Each test case contains a single integer $$$N$$$ — $$$P$$$ is the set of the smallest $$$N$$$ prime numbers.

  • $$$1\leq T\leq 4\times 10^5$$$
  • $$$1\leq N\leq 4\times 10^5$$$
  • It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \times 10^6$$$.
Output

For each test case, print a string $$$S$$$ of length $$$N$$$ consisting of characters A and B, representing the optimal partition. If the $$$k$$$-th smallest prime, $$$p_k$$$, belongs to $$$A$$$ in your solution, the $$$k$$$-th character of $$$S$$$ must be A, and it must be B otherwise. If there are multiple such partitions, print any of them.

Example
Input
5
3
4
4
9
10
Output
AAB
ABBA
ABBA
ABAABABBA
BABABABAAB