题目描述

给定一个整数 $k$。请你找到最大的整数 $x$，其中 $1 \le x < k$，使得 $x! + (x - 1)!$ 是 $k$ 的倍数。如果不存在这样的 $x$，输出 $-1$。

$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$。

如果 $a$ 和 $b$ 是整数，当且仅当存在整数 $c$ 使得 $a = b \cdot c$ 时，称 $a$ 是 $b$ 的倍数。例如，$10$ 是 $5$ 的倍数，但 $9$ 不是 $6$ 的倍数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来每个测试用例包含一行，一个整数 $k$（$2 \le k \le 10^9$）。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的最大的 $x$。如果不存在这样的 $x$，输出 $-1$。

说明/提示

在第一个测试用例中，$2! + 1! = 2 + 1 = 3$，$3$ 是 $3$ 的倍数。

在第三个测试用例中，$7! + 6! = 5040 + 720 = 5760$，$5760$ 是 $8$ 的倍数。

由 ChatGPT 4.1 翻译

样例

4
3
6
8
10

2
5
7
9