Problem Description

Ancient people believed that $666$ is a number that belongs to the devil.

Moreover, as long as a number’s decimal representation contains three consecutive $6$’s, ancient people also considered it a devil number, such as $666,1666,6663,16666,6660666$, and so on.

Ancient texts often use “the $X$-th smallest devil number” to refer to these numbers, which causes great inconvenience for researchers.

Now please write a program that, given $X$, outputs the corresponding devil number.

Input Format

The first line contains an integer $T$, meaning there are $T$ groups of testdata.

Each group of testdata takes one line and contains an integer $X$.

Output Format

For each group of testdata, output one line containing a devil number.

3
2
3
187

1666
2666
66666

Hint

Constraints: $1 \le T \le 1000$, $1 \le X \le 5 \times 10^7$.

Translated by ChatGPT 5