Problem Statement

A Kadomatsu sequence is a sequence $A_1, A_2, A_3$ of $3$ elements that satisfies the following 2 conditions.

• $A_1, A_2, A_3$ are all distinct
• Among the $3$ elements, $A_2$ is the largest or $A_2$ is the smallest

Let $X_i$ be the $i$-th digit from the top of an $N$-digit ($3 \leq N$) positive integer $X$.
If the sequences $X_i$, $X_{i+1}$, $X_{i+2}$ ($1 \leq i \leq N-2$ ) are all Kadomatsu sequences, $X$ is a Kadomatsu number.
For example, 4514 and 893 are Kadomatsu numbers, but 114514 and 89 are not Kadomatsu numbers.

When $X$ is a Kadomatsu number and there exist $K$ Kadomatsu numbers smaller than $X$, $X$ is said to be the $K+1$-th Kadomatsu number.
The 1st Kadomatsu number is 102, the 404th Kadomatsu number is 893, and the 1000th Kadomatsu number is 3296.

Given a positive integer $K$ ($1 \leq K \leq 10^{10}$), find the $K$-th Kadomatsu number.

Input

$T$

$K$

All inputs are integers.

Output

For each test case, output the $K$-th Kadomatsu number on one line.

Sample

5
1
2
3
4
5

102
103
104
105
106

4
114
215
404
1000

328
514
893
3296

1
10000000000

37294859064823