我们说正整数 $$$n$$$ 是 $$$k$$$ - 对于某些正整数 $$$k$$$ 有好处,如果 $$$n$$$ 可以表示为 $$$k$$$ 正整数的和,当除以 $$$k$$$ 时给出 $$$k$$$ 不同的余数。
给定一个正整数 $$$n$$$,找到一些 $$$k \geq 2$$$ 使得 $$$n$$$ 是 $$$k$$$-good 或告诉这样的 $$$k$$$ 不存在。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。
每个测试用例由一行和一个整数 $$$n$$$ ($$$2 \leq n \leq 10^{18}$$$) 组成。
输出
对于每个测试用例,打印一行,其值为 $$$k$$$,使得 $$$n$$$ 为 $$$k$$$-good ($$$k \geq 2$$$),或者如果 $$$n$$$ 对于任何 $$$k$$$ 不是 $$$k$$$-good,则为 $$$-1$$$。如果 $$$k$$$ 有多个有效值,则可以打印其中任何一个。
示例
输入 #1
5 2 4 6 15 20
输出 #1
-1 -1 3 3 5
注意
$$$6$$$ 是一个 $$$3$$$ 好数字,因为它可以表示为 $$$3$$$ 数字的总和,这些数字除以 $$$3$$$ 时会给出不同的余数:$$$6 = 1 + 2 + 3$$$。
$$$15$$$ 也是一个 $$$3$$$ 好数字,因为 $$$15 = 1 + 5 + 9$$$ 和 $$$1, 5, 9$$$ 除以 $$$3$$$ 时给出不同的余数。
$$$20$$$ 是一个 $$$5$$$ 的好数,因为 $$$20 = 2 + 3 + 4 + 5 + 6$$$ 和 $$$2,3,4,5,6$$$ 除以 $$$5$$$ 时得到不同的余数。