Falling Number Query

Let \(f\colon \mathbb{N}^{+} \to \mathbb{N}^{+}\) be a function defined as follows. Write a positive integer \(x\) in its decimal representation. Let \(a_i\) denote the \(i\)-th digit of \(x\) when read from the least significant digit to the most significant digit (so that \(a_1\) is the units digit, \(a_2\) is the tens digit, etc.). Let \(len\) be the number of digits of \(x\) and define \[ f(x)=\prod_{i=1}^{len} (a_i+1). \] A number \(x\) is called a falling number if there exists some \(y\) such that \(f(y)=x\).

You are given \(Q\) queries. In the \(i\)-th query a positive integer \(k\) is given. Let \(x\) be the \(k\)-th smallest falling number (when falling numbers are sorted in increasing order). Your task is to find the smallest \(y\) (with \(1\le y\le10^{18}\)) such that \(f(y)=x\). If no such \(y\) in the range \([1,10^{18}]\) exists, output -1.

Note:
For a falling number \(x\), there may be several valid \(y\). You must output the smallest valid \(y\) in the range \([1,10^{18}]\).

Recall that if \(x\) has digits \(a_1,a_2,\dots,a_{len}\) (from least significant to most significant) then \[ f(x)=\prod_{i=1}^{len}(a_i+1). \]

inputFormat

The first line contains an integer \(Q\) \((1\le Q\le 10^5)\) representing the number of queries. Each of the following \(Q\) lines contains one positive integer \(k\). It is guaranteed that \(k\ge 1\).

Note: The input file is given in plain text.

outputFormat

For each query, output one line containing the answer: the smallest \(y\) (with \(1\le y\le 10^{18}\)) such that \(f(y)\) equals the \(k\)-th smallest falling number. If no such \(y\) exists, output -1.

sample

3
1
5
10

1
5
15