A15651. Greatest Convex

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

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