给你一个整数 $$$k$$$。找到最大的整数$$$x$$$,其中$$$1 \le x < k$$$,这样$$$x! + (x - 1)!^\dagger$$$ 是 $$$^\ddagger$$$ $$$k$$$ 的倍数,或者确定不存在这样的 $$$x$$$。
$$$^\dagger$$$ $$$y!$$$ 表示 $$$y$$$ 的阶乘,递归定义为 $$$y! = y \cdot (y-1)!$$$ 对于 $$$y \geq 1$$$,基本情况为 $$$0! = 1$$$。例如,$$$5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120$$$。
$$$^\ddagger$$$ 如果 $$$a$$$ 和 $$$b$$$ 是整数,则 $$$a$$$ 是 $$$b$$$ 的倍数,如果存在整数 $$$c$$$ 使得 $$$a = b \cdot c$$$。例如,$$$10$$$ 是 $$$5$$$ 的倍数,但 $$$9$$$ 不是 $$$6$$$ 的倍数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$k$$$ ($$$2 \le k \le 10^9$$$)。
输出
对于每个测试用例,输出一个整数 - 满足上述条件的最大可能整数 $$$x$$$。
如果不存在这样的$$$x$$$,则输出$$$-1$$$。
示例
输入 #1
4 3 6 8 10
输出 #1
2 5 7 9
注意
在第一个测试用例中,$$$2! + 1! = 2 + 1 = 3$$$,它是 $$$3$$$ 的倍数。
在第三个测试用例中,$$$7! + 6! = 5040 + 720 = 5760$$$,它是 $$$8$$$ 的倍数。