A. Greatest Convextime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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).OutputFor each test case output a single integer — the largest possible integer x that satisfies the conditions above. If no such x exists, output -1.ExampleInput
436810Output
2
5
7
9
NoteIn 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.
436810
2 5 7 9 
['greedy', 'math', 'number theory', '*800']