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 10\,000~.

Subtask	Points	~n~
1	5	~1 \le n \le 10~
2	15	~1 \le n \le 100~
3	40	~1 \le n \le 10\,000~
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, 6\,969, 42\,069, 69\,420, 420\,420$$

The ~3^\text{rd}~ term of the sequence is ~6\,969~.

The ~5^\text{th}~ term of the sequence is ~69\,420~.

Red herring.