背景

下坠是有终点的吗？

题目描述

$f$ 是定义在 $\mathbb{N^+}$ 上的函数。

我们令 $a_i$ 表示 $x$ 从低到高第 $i$ 位，那么 $f(x)= \prod_{i=1}^{len} (a_i+1)$（$len$ 表示 $x$ 的位数）。

如果对于一个数 $x$，存在 $y$ 使得 $f(y)=x$，那我们称 $x$ 是下坠数。

现在有 $Q$ 次询问，每次询问会给出一个正整数 $k$。

令 $x$ 表示所有下坠数中第 $k$ 小的下坠数，那么请你找到一个最小的 $y$，使得 $f(y)=x$。若不存在一个 $y \in [1,10^{18}]$ 满足条件，则输出 $-1$。

输入格式

第一行输入一个整数 $Q$，表示询问次数。

接下输入一行 $Q$ 个数，第 $i$ 个数表示第 $i$ 次询问的 $k$。

输出格式

输出一行 $Q$ 个数，第 $i$ 个数表示第 $i$ 次询问你找到的答案。

3
1 2 3

1 2 3

3
9 14 46666666

9 18 -1

提示

样例解释 #1

注意到 $f$ 的定义域是 $\mathbb{N^+}$，所以 $1$ 不是下坠数。则前三个下坠数分别为 $2,3,4$，对应的 $y$ 值则为 $1,2,3$。

样例解释 #2

第 $9$ 和 $14$ 个下坠数分别为 $10$ 和 $18$，其对应的 $y$ 值则为 $9$ 和 $18$。可以证明，第 $46666666$ 个下坠数对应的 $y > 10^{18}$。

数据范围

对于 $100\%$ 的数据满足：$Q \leq 10^5$，$k \leq 5 \times 10^7$。

其中对于 $10\%$ 的数据满足：$k \leq 100$。

对于 $30\%$ 的数据满足：$k \leq 5 \times 10^3$。

对于另外 $20\%$ 的数据满足：对于所有被询问到的下坠数 $x$，都有 $\vert x-y \vert \leq 100$ 或者 $y > 10^{18}$。

请注意不同寻常的时间限制。