A. Greatest Convex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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

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

Example
Input
4
3
6
8
10
Output
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$$$.