Problem Statement

You are given an integer sequence $X=(X_1,X_2,\cdots,X_N)$ of length $N$ consisting of $0$ and $1$.

You can perform the following operation zero or more times:

• Classify each element of $X$ into group A or group B. Then, for each group, reverse the order of the elements it contains. More formally, if the elements contained in a group are $X_{i_1},X_{i_2},\cdots,X_{i_s}$ ($i_1<i_2<\cdots<i_s$), then for all $1 \leq j \leq s$, simultaneously replace the value of $X_{i_j}$ with $X_{i_{s+1-j}}$.

Your goal is to make $X$ non-decreasing. Find the minimum number of operations needed to achieve the goal and the way to perform the operations. It can be proved that a solution always exists under the constraints of this problem.

Solve $T$ cases for one input.

Constraints

• $1 \leq T \leq 250000$
• $1 \leq N \leq 250000$
• $0 \leq X_i \leq 1$
• The sum of $N$ over the $T$ cases is at most $250000$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N
X_1 X_2 \cdots X_N

Output

For each case, output in the following format:

k
s_1
s_2
\vdots
s_k

Here, $k$ is the minimum number of operations needed, and $s_i$ is a string representing the $i$-th operation. $s_i$ is a string of length $N$ consisting of A and B, and the $j$-th character of $s_i$ represents the group to which $X_j$ is assigned in the $i$-th operation. If there are multiple solutions, you may output any of them.