#P1768A. Greatest Convex

Greatest Convex

Description

You are given an integer kk. Find the largest integer xx, where 1x<k1 \le x < k, such that x!+(x1)!x! + (x - 1)!^\dagger is a multiple of ^\ddagger kk, or determine that no such xx exists.

^\dagger y!y! denotes the factorial of yy, which is defined recursively as y!=y(y1)!y! = y \cdot (y-1)! for y1y \geq 1 with the base case of 0!=10! = 1. For example, 5!=543210!=1205! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120.

^\ddagger If aa and bb are integers, then aa is a multiple of bb if there exists an integer cc such that a=bca = b \cdot c. For example, 1010 is a multiple of 55 but 99 is not a multiple of 66.

The first line contains a single integer tt (1t1041 \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 kk (2k1092 \le k \le 10^9).

For each test case output a single integer — the largest possible integer xx that satisfies the conditions above.

If no such xx exists, output 1-1.

Input

The first line contains a single integer tt (1t1041 \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 kk (2k1092 \le k \le 10^9).

Output

For each test case output a single integer — the largest possible integer xx that satisfies the conditions above.

If no such xx exists, output 1-1.

Sample Input 1

4
3
6
8
10

Sample Output 1

2
5
7
9

Note

In the first test case, 2!+1!=2+1=32! + 1! = 2 + 1 = 3, which is a multiple of 33.

In the third test case, 7!+6!=5040+720=57607! + 6! = 5040 + 720 = 5760, which is a multiple of 88.