J. The test cases
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
unique.in
output
standard output

You may think that generating test cases for problems is always an easy task, but sometimes creating tests for a problem is more interesting than the problem itself. The judges of the ECPC came up with a nice problem that needs a binary string with the following properties as its input.

  1. The string should be with an even length N.
  2. The decimal number represented by it should be divisible by N.
  3. All decimal numbers represented by its prefixes should give unique remainders after being divided by N.

The task of creating an input generator for this problem was assigned to Ayman, and after some work on the task, Ayman convinced the judges that his task is more interesting than the problem itself. That's why all of them decided to include this task in the problem set. So given a number N, can you print a binary string that satisfies the three properties?. If there are multiple answers print any. It can be proven that an answer always exists.

Input

The first line of the input is the number of test cases T. Each test case contains a single line with the integer N, where 2 ≤ N ≤ 105.

Output

For each test case output a single line with any valid binary string that satisfies the three mentioned properties.

Example
Input
2
4
10
Output
1100
1100010110
Note

In the first test case for N = 4, one of the possible answers is 1100, because the decimal number represented by 1100 is 12 which is divisible by 4. Also the prefixes of 1100 are 1, 11, 110 and 1100 and their decimal representations are 1, 3, 6, 12 respectively.

You can see that all of their decimal representations produce different remainders when divided by 4 which are 1, 3, 2 and 0 respectively.