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