P8982 "DROI" Round 1 Falling

Does falling have an end?

$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$.

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 one line with $Q$ numbers. The $i$-th number is the answer you found for the $i$-th query.

#### 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