You are given an integer $a$. Find the smallest positive integer $b$ ($b \ge 1$) such that $a+b$ is a divisor of $a \cdot b$.

It can be proven that, under the given constraints, a solution always exists.

Input

Each test contains multiple testcases. The first line of each testcase contains an integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains one integer $a$ ($2 \le a \le 10^9$).

Output

For each testcase, print the smallest integer $b \ge 1$ such that $a+b$ is a divisor of $a \cdot b$.

Example

stdin

14
2
3
4
5
6
7
8
9
10
11
12
13
14
15

stdout

2
6
4
20
3
42
8
18
10
110
4
156
14
10