Count-And-Say is a sequence of numbers given below:

1. 1
2. 11
3. 21
4. 1211
5. 111221

This sequence starts with 1.

1 is read as one 1 → 11

11 is read as two 1 → 21

21 is read as one 2, one 1 → 1211

1211 is read as one 1, one 2, two 1 → 111221

And so on…

Given a number n, find the n^th sequence.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has one line with an integer ‘n’.

Output Format

For each test case, the output has a line with a string ‘s’ denoting the value of countAndSay(n).

Sample Input

3
2
4
6

Expected Output

11
1211
312211

Constraints

1 <= T <= 40
1 <= n <= 40