题目内容

在某个数字王国中，每一个正整数都被赋予一个“等级”，其值定义为该数的十进制表示中数字的个数（不含前导零）。记正整数 $N$ 的等级为 $\ell(N)$。例如 $\ell(7)=1$，$\ell(120)=3$。

定义 $N$ 的“能量值”为 $N \times \ell(N)$。现在给定一个目标能量值 $S$，请你判断是否存在一个正整数 $N$，使得 $N \times \ell(N) = S$。如果存在，请输出任意一个满足条件的 $N$；否则输出 $-1$。

约束：

• 测试数据组数 $T$ 满足 $1 \le T \le 2 \times 10^5$。
• 每个目标能量值 $S$ 满足 $1 \le S \le 10^{18}$。
• 输出的 $N$ 必须满足 $1 \le N \le 10^{18}$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来 $T$ 行，每行包含一个整数 $S$，表示目标能量值。

输出描述

对于每组测试数据，输出一行一个整数。若存在满足条件的 $N$，则输出 $N$；否则输出 $-1$。

样例1

输入

3
7
14
20

输出

7
-1
10

说明

第一组数据 S = 7：枚举数位长度 $d = 1$，此时 $N = 7 / 1 = 7$，$N$ 的十进制位数 $\ell(N) = 1$，满足 $N \times \ell(N) = 7$，输出 7。

第二组数据 S = 14：$d = 1$ 时 $N = 14$，$\ell(14) = 2 eq 1$；$d = 2$ 时 $N = 7$，$\ell(7) = 1 eq 2$；其余 $d$ 不能整除 14，无解，输出 -1。

第三组数据 S = 20：$d = 2$ 时 $N = 20 / 2 = 10$，$\ell(10) = 2$，$10 \times 2 = 20$，满足条件，输出 10。

样例2

输入

4
1
100
1000
1000000000000000000

输出

1
50
-1
-1

说明

第一组 S = 1：$d = 1$，$N = 1$，$\ell(1) = 1$，输出 1。

第二组 S = 100：$d = 2$ 时 $N = 100 / 2 = 50$，$\ell(50) = 2$，$50 \times 2 = 100$，输出 50。

第三组 S = 1000：枚举所有可能的位数 $d \in [1,4]$。$d=1$ 得 $N=1000$，位数为 $4 eq 1$；$d=2$ 得 $N=500$，位数为 $3 eq 2$；$d=3$ 时 1000 不能被 3 整除；$d=4$ 得 $N=250$，位数为 $3 eq 4$。无解，输出 -1。

第四组 S = 10^{18}：同样枚举所有 $d \in [1,18]$，均无法得到十进制位数与除数一致的 $N$，输出 -1。

样例3

输入

2
90
999

输出

45
333

说明

第一组 S = 90：$d = 2$ 时 $N = 90 / 2 = 45$，$\ell(45) = 2$，$45 \times 2 = 90$，输出 45。

第二组 S = 999：$d = 3$ 时 $N = 999 / 3 = 333$，$\ell(333) = 3$，$333 \times 3 = 999$，输出 333。