# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Poltu and Interesting Number

By RamprosadG · Limits 1s, 512 MB

Poltu Loves interesting number. So he wants to find this type of number.

The definition of an interesting number is described below-

An Interesting number is a number that contains digits (1 - 9). It does not contain 2 consecutive same digit. The first few such numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19, 21, 23, 24 and so on.

You are given n. You have to calculate the n-th interesting number.

## Input

Input starts with an integer T(1 ≤ T ≤ 10000), denoting the number of test cases.

Each case contains an integer n(1 ≤ n ≤ 1000000000000).

## Output

For each case, print the case number and the n-th interesting number.

## Sample

InputOutput
4
5
10
15
20
Case 1: 5
Case 2: 12
Case 3: 17
Case 4: 24


Note: Dataset id huge, use faster input, ouput.

### Statistics

52% Solution Ratio

mahdi.hasnatEarliest, Dec '19

habijabiFastest, 0.0s

EgorKulikovLightest, 393 kB

habijabiShortest, 639B