Numbers can be classified as IAR numbers and FA numbers.

Numbers in which all digits are equal to either adjacent digit are called In-A-Relationship numbers. For example: 11, 22, 111, 9922888 and 777788822 are IAR numbers.

Numbers featuring lonely digits are called Forever-Alone (FA) numbers. For example: in 22122 digit 1 is alone and in 123 all digits are alone.

Given K, your task is to find the Kth In-A-Relationship (IAR) number.

Input

The first line contains number of test cases T (T <= 50)

Then T test cases follow.

Each line contains one integer K (1 <= K <= 5*10^6)

Output

For each test case, print the Kth IAR number.

Sample

Input:
5
1
2
3
10
12

output:
11
22
33
111
333