CF1768A.Greatest Convex

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given an integer $k$ . Find the largest integer $x$ , where $1 \le x < k$ , such that $x! + (x - 1)!^\dagger$ is a multiple of $^\ddagger$ $k$ , or determine that no such $x$ exists.

$^\dagger$ $y!$ denotes the factorial of $y$ , which is defined recursively as $y! = y \cdot (y-1)!$ for $y \geq 1$ with the base case of $0! = 1$ . For example, $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120$ .

$^\ddagger$ If $a$ and $b$ are integers, then $a$ is a multiple of $b$ if there exists an integer $c$ such that $a = b \cdot c$ . For example, $10$ is a multiple of $5$ but $9$ is not a multiple of $6$ .

输入格式

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer $k$ ( $2 \le k \le 10^9$ ).

输出格式

For each test case output a single integer — the largest possible integer $x$ that satisfies the conditions above.

If no such $x$ exists, output $-1$ .

输入输出样例

输入#1
```
4
3
6
8
10
```
输出#1
```
2
5
7
9
```

说明/提示

In the first test case, $2! + 1! = 2 + 1 = 3$ , which is a multiple of $3$ .

In the third test case, $7! + 6! = 5040 + 720 = 5760$ , which is a multiple of $8$ .

首页