A fool and his sequence.

The special April contests have just ended, but the problem setters are still marveling over the yearly event.

For example, a Fool's number is an attractive positive integer. A Fool's number has the interesting property that, in its decimal representation, it is possible to insert spaces to form a series of $69$'s and $420$'s, without any other additional garbage.

A problem setter defines the Fool's sequence, which contains every Fool's number in strictly increasing order, with no additional terms that are not Fool's numbers (what is the fun if the $x^{\text{th}}$ term is $x$?). The first term is $69$ and the second term is $420$.

However, the sequence grows quite strangely, and it is hard to list the sequence! What is the $n^{\text{th}}$ term of the Fool's sequence? Since there is no point in knowing just one term, you want to repeat this process $T$ times in total.

Constraints

In all subtasks, $1\le T\le 10000$.

Subtask	Points	$n$
1	5	$1\le n\le 10$
2	15	$1\le n\le 100$
3	40	$1\le n\le 10000$
4	20	$1\le n\le {10}^7$
5	20	$1\le n\le {10}^{15}$

Input Specification

The first line contains one integer, $T$.

The next $T$ lines contain a single integer, $n$.

Output Specification

Output the $n^{\text{th}}$ term of the Fool's sequence on a new line.

Sample Input

2
3
5

Sample Output

6969
69420

Explanation for Sample Output

The first $6$ terms of the Fool's sequence are:

$${\displaystyle 69,420,6969,42069,69420,420420}$$

The $3^{\text{rd}}$ term of the sequence is $6969$.

The $5^{\text{th}}$ term of the sequence is $69420$.

Red herring.