Background

Does falling have an end?

Problem Description

$f$ is a function defined on $\mathbb{N^+}$.

Let $a_i$ be the $i$-th digit of $x$ from low to high. Then $f(x)= \prod_{i=1}^{len} (a_i+1)$, where $len$ is the number of digits of $x$.

For a number $x$, if there exists $y$ such that $f(y)=x$, then we call $x$ a falling number.

Now there are $Q$ queries. Each query gives a positive integer $k$.

Let $x$ be the $k$-th smallest falling number among all falling numbers. Please find the smallest $y$ such that $f(y)=x$. If there is no $y \in [1,10^{18}]$ that satisfies the condition, output $-1$.

Input Format

The first line contains an integer $Q$, the number of queries.

The next line contains $Q$ numbers. The $i$-th number is the $k$ for the $i$-th query.

Output Format

Output one line with $Q$ numbers. The $i$-th number is the answer you found for the $i$-th query.

3
1 2 3

1 2 3

3
9 14 46666666

9 18 -1

Hint

Sample Explanation #1

Note that the domain of $f$ is $\mathbb{N^+}$, so $1$ is not a falling number. Therefore, the first three falling numbers are $2,3,4$, and the corresponding $y$ values are $1,2,3$.

Sample Explanation #2

The $9$-th and $14$-th falling numbers are $10$ and $18$, and their corresponding $y$ values are $9$ and $18$. It can be proven that the $46666666$-th falling number corresponds to $y > 10^{18}$.

Constraints

For $100\%$ of the testdata: $Q \leq 10^5$, $k \leq 5 \times 10^7$.

For $10\%$ of the testdata: $k \leq 100$.

For $30\%$ of the testdata: $k \leq 5 \times 10^3$.

For another $20\%$ of the testdata: for every queried falling number $x$, we have $\vert x-y \vert \leq 100$ or $y > 10^{18}$.

Please note the unusual time limit.

Translated by ChatGPT 5