Chef built a binary string S that has exactly N hills and M valleys.

A hill is any index 1 < i < |S| such that both its neighbors are strictly smaller than it, i.e, S_{i-1} < S_{i} and S_{i+1} < S_{i}.

A valley is any index 1 < i < |S| such that both its neighbors are strictly larger than it, i.e, S_{i-1} > S_{i} and S_{i+1} > S_{i}.

Chef thinks that his string S is the shortest among all binary strings with N hills and M valleys. You don't quite trust his words, so to verify his claim you would like to find the shortest binary string with exactly N hills and M valleys.

If there are multiple possible binary strings of the least length satisfying the given condition, you may print any of them.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains two space-separated integers N and M, the required number of hills and valleys respectively.

------ Output Format ------

For each test case, output two lines.
- The first line contains the length of the binary string you constructed to satisfy the given conditions.
- The second line contains the string itself.

------ Constraints ------

$1 ≤ T ≤ 2500$
$1 ≤ N ≤ 500$
$1 ≤ M ≤ 500$
- The sum of lengths of the answer strings across all test cases does not exceed $2\cdot 10^{5}$

------ subtasks ------

Subtask 1 (10 points):
$1 ≤ N ≤ 50$
$1 ≤ M ≤ 50$
You may output any string of length not exceeding $320$ containing exactly $N$ hills and $M$ valleys: it need not be shortest by length. It is guaranteed that at least one such string with length $≤ 320$ exists.

Subtask 2 (90 points):
Original constraints
The binary string you construct must be shortest by length.

----- Sample Input 1 ------
3
3 2
2 3
3 3
----- Sample Output 1 ------
7
0101010
7
1010101
8
01010101
----- explanation 1 ------
Test case $1$: The given string has hills at indices $2, 4, 6$ and valleys at indices $3, 5$. It can be verified that there is no string of length $6$ or less with $3$ hills and $2$ valleys. Note that for subtask $1$, a binary string like $001010100$ will also be accepted as a valid output, even though it is not shortest by length.

Test case $3$: Apart from the given string, another possible string of length $8$ that has $3$ hills and $3$ valleys is $10101010$. You may print any of them.

见题面

见题面