BYU Algorithm Challenge 5.0

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence. The sequence is 1-indexed, so the first spot is index 1, not 0.

Note: The sequence of integers will be represented as a string.

Input

The first line will contain an integer n indicating the number of test cases to follow. On each line, there will be a test case consisting of an integer.

Output

The count and say version of each test case.

Example

Input:
2
1
4

Output:
1
1211