让我们用 $$$d(n)$$$ 表示数字 $$$n$$$ 的所有约数之和,即 $$$d(n) = \sum\limits_{k | n} k$$$。
例如,$$$d(1) = 1$$$、$$$d(4) = 1+2+4=7$$$、$$$d(6) = 1+2+3+6=12$$$。
对于给定数字 $$$c$$$,找到满足 $$$d(n) = c$$$ 的最小值 $$$n$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例都由一个整数$$$c$$$ ($$$1 \le c \le 10^7$$$) 来表征。
输出
对于每个测试用例,输出:
- 如果不存在 $$$d(n) = c$$$ 这样的 $$$n$$$,则为“-1”;
- $$$n$$$,否则。
示例
输入 #1
12 1 2 3 4 5 6 7 8 9 10 39 691
输出 #1
1 -1 2 3 -1 5 4 7 -1 -1 18 -1