Greatest Convex (Codeforces 1768A)
Tags: Greedy, number theory

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

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

Sample Inputs:
4
3
6
8
10

Sample Outputs:
2
5
7
9

Solution (Python):
for x in [*open(0)][1:]:
    print(int(x) - 1)

Solution (Python):
for i in [*open(0)][1:]:
    print(int(i) - 1)

Solution (Python):
for i in [*open(0)][1:]:
    print(int(i) - 1)