#ALONE. FOREVER ALONE

FOREVER ALONE

IAR and FA numbers

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

Sample output

11

22

33

111

333