ALONE - FOREVER ALONE

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

Added by:cegprakash
Date:2013-01-23
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF
Resource:problem setter: rishi_kumar

hide comments
2013-03-16 05:21:55 Digvijay Karamchandani
@ceg prakash Loved solving this problem.. kudos :)

reply: credit goes to rishi_kumar

Last edit: 2013-12-12 22:36:34
2013-03-16 05:21:55 Ehor Nechiporenko
Hey, I love this one.
Good example of nice <censored> problem.

<Please, no spoilers in comments. Even if they would seem obvious to you.>

Last edit: 2013-01-28 19:56:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.