I. Weird Divisibility

Time limit: 1.5s Memory limit: 256MB Input: Output:

You are given an integer aa. Find the smallest positive integer bb (b1b \ge 1) such that a+ba+b is a divisor of aba \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 tt (1t1041 \le t \le 10^4) — the number of testcases.

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

Output

For each testcase, print the smallest integer b1b \ge 1 such that a+ba+b is a divisor of aba \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

Log in or sign up to be able to send submissions!