Codeforces Round 800 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

implementation

*800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Creep

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDefine the score of some binary string $$$T$$$ as the absolute difference between the number of zeroes and ones in it. (for example, $$$T=$$$ 010001 contains $$$4$$$ zeroes and $$$2$$$ ones, so the score of $$$T$$$ is $$$|4-2| = 2$$$).

Define the creepiness of some binary string $$$S$$$ as the maximum score among all of its prefixes (for example, the creepiness of $$$S=$$$ 01001 is equal to $$$2$$$ because the score of the prefix $$$S[1 \ldots 4]$$$ is $$$2$$$ and the rest of the prefixes have a score of $$$2$$$ or less).

Given two integers $$$a$$$ and $$$b$$$, construct a binary string consisting of $$$a$$$ zeroes and $$$b$$$ ones with the minimum possible creepiness.

Input

The first line contains a single integer $$$t$$$ $$$(1\le t\le 1000)$$$ — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$ 1 \le a, b \le 100$$$) — the numbers of zeroes and ones correspondingly.

Output

For each test case, print a binary string consisting of $$$a$$$ zeroes and $$$b$$$ ones with the minimum possible creepiness. If there are multiple answers, print any of them.

Example

Input

5 1 1 1 2 5 2 4 5 3 7

Output

10 011 0011000 101010101 0001111111

Note

In the first test case, the score of $$$S[1 \ldots 1]$$$ is $$$1$$$, and the score of $$$S[1 \ldots 2]$$$ is $$$0$$$.

In the second test case, the minimum possible creepiness is $$$1$$$ and one of the other answers is 101.

In the third test case, the minimum possible creepiness is $$$3$$$ and one of the other answers is 0001100.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 04:57:09 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|