Description

Alice and Bob play a game.

Alice initially has $n$ stones, and Bob initially has $m$ stones. They play for several rounds. In round $i$, the loser gives the winner $i$ stones. The game stops when, in some round, the loser does not have enough stones.

Given $n, m$, find the maximum number of rounds the game can be played (not including the ending round), and construct a win-loss sequence containing only A and B such that the length of the sequence equals your answer, and at any time the number of stones each person has is non-negative.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

One line contains $2$ non-negative integers $n, m$.

Output Format

For each test case:

The first line contains an integer, representing the maximum number of rounds the game can be played. Let your answer be $x$.

The second line contains a string of length $x$, representing the win-loss sequence.

If Alice wins round $i$, then the $i$-th character of your sequence is A. If Bob wins round $i$, then the $i$-th character is B.

3
1 1
0 3
1 3

2
BA
3
AAB
3
ABA

Hint

This problem uses bundled tests.

• Subtask 1 (6 points): $n+m\le15$.
• Subtask 2 (8 points): $n=m$.
• Subtask 3 (8 points): $\sum n+m\le10^3$.
• Subtask 4 (8 points): $\sum n+m\le2\times10^4$.
• Subtask 5 (25 points): $\sum n+m\le4\times10^5$.
• Subtask 6 (45 points): No special constraints.

For $100\%$ of the testdata, $1\le T\le10^3$, $0\le n,m\le2\times10^7$, $1\le n+m\le2\times10^7$, $\sum n+m\le2\times10^7$.

If you correctly answer the maximum number of rounds, but your constructed win-loss sequence is invalid, you will get $20\%$ of the score for that test point (rounded down).

Note that if you cannot construct a win-loss sequence, you still need to output a non-empty string.

The output size of this problem is large, so please use a fast output method.

Translated by ChatGPT 5