TLE '16 Contest 8 P3 - Fool's Sequence

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types
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^{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^{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 Format

The first line contains one integer, T.

The next T lines contain a single integer, n.

Output Format

Output the n^{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^{rd} term of the sequence is 6969.

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

Red herring.


Comments

There are no comments at the moment.