← 返回题目列表

Codeforces · 1768/A

A. 最大凸

中文机器翻译题面 查看原题

给你一个整数 $$$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$$$ 的倍数。