TLE '16 Contest 8 P3 - Fool's Sequence

View as PDF

Submit solution

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

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^\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.


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


Sample Output


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.


There are no comments at the moment.