Greatest Convex
Description
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$.
Input
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$).
Output
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$.
4
3
6
8
10
2
5
7
9
Note
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$.