I. Weird Divisibility
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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
Input
14
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Output
2
6
4
20
3
42
8
18
10
110
4
156
14
10