Ravi and Micro, two very good friends, had a fight today. So, Ravi challenges Micro to beat him in a game.
Ravi takes a number n to start the game.
Now, Ravi will choose integers from 0 to n sequentially (i.e.in the turn 0 he choses 0, in turn 1 he choses 1, ans so on till nth turn when he choses n).We will call this integer r for each turn.
For each turn ,the possible integers Micro can choose(in each turn, Micro can choose any number of integers) are represented by m(0 ≤ m ≤ n)

The rules of the game are:
If r+m=n, then Ravi gets r and Micro gets m(value=m , informally value is the part of n which Micro gets).
If r+m<n, then Ravi gets r and Micro gets m and remaining is not used.(value=m) If r+m>n and:
i. If r<m, Ravi gets r , Micro gets n-r.(value=n-r) ii.If r>m, Micro gets m, Ravi gets n-m.(value=m)
iii.If r=m,Ravi and Micro each get n/2(may be floating number).(value=n/2)

For each of the turns, Micro has to choose a set of integers(set may be singleton) such that for all the elements in the set, he gets a single value(see rules for clarification of value) which is the maximum possible value he can get when Ravi has chosen r. We call this set as M.

for given r, M={all those m for which value is maximum}.

Let the size of M in turn 0 be s0.
For r=1, size be s1 , and so on.

You have to print a number as: s0s1s2s3......sn to help Micro, a dear friend of yours.

Example:

n=2

Now, Ravi choses integers from 0 to 2.

When Ravi chooses 0:
If Micro chooses 0, value=0
If he chooses 1, value=1
If he chooses 2, value=2

So, for r=0, M={2} as value for 2 is maximum, s0=1

When Ravi chooses 1:
If Micro chooses 0, value=0
If he chooses 1, value=1
If he chooses 2, value=1 as r=1,m=2 so r+m>n ans r

So, for r=1, M={1,2} as value=1 for both which is maximum for r=1. s1=2

When Ravi chooses 2:
If Micro chooses 0, value=0
If Micro chooses 1, r=2,m=1 , value=m=1 as r+m>n and m
If Micro chooses 2, r=2,m=2 value=1 as r+m>n and r=m so , value=n/2=2/2=1

So, for r=2, M={1,2} as value=1 for both. s2=2

So, answer for n=2 will be s0s1s2 which is 122.

Input:
The first line contains t (number of test cases).
The following t lines contain n in each line.

Output:
As specified in the question.

Constraints:
1 ≤ t ≤ 100
0 ≤ n ≤ 100000

SAMPLE INPUT
1
2

SAMPLE OUTPUT
122

见题面

见题面