CF 1768A - Greatest Convex

You are given an integer k. Find the largest integer x, where 1≤x<k, such that x!+(x−1)!† is a multiple of ‡ k

, or determine that no such x exists.† y! denotes the factorial of y, which is defined recursively as y!=y⋅(y−1)!

 for y≥1 with the base case of 0!=1. For example, 5!=5⋅4⋅3⋅2⋅1⋅0!=120.

‡ If a and b are integers, then a is a multiple of b if there exists an integer c

 such that a=b⋅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≤t≤104) — the number of test cases. The description of test cases follows.

The only line of each test case contains a single integer k (2≤k≤109).

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.

Is x=k−1 always suitable?

The answer is yes, as x!+(x−1)!=(x−1)!×(x+1)=((k−1)−1)!×((k−1)+1)=(k−2)!×(k)

, which is clearly a multiple of k

.

Therefore, x=k−1

 is the answer.

Time complexity: O(1)

一旦计算出来k-1是最大值，那么问题就很简单了；

下面是代码：