D. Taffy's LCM
time limit per test
1 second
memory limit per test
1024 MB
input
standard input
output
standard output

Taffy gives you an integer $$$c$$$.

You need to help Taffy find two positive integers $$$a$$$ and $$$b$$$ such that $$$a + b = c$$$, and their least common multiple $$$\text{lcm}(a, b)$$$ is maximized.

The least common multiple of two positive integers $$$a$$$ and $$$b$$$ is the smallest positive integer that is divisible by both $$$a$$$ and $$$b$$$.

Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$).

Each test case consists of a single line containing one integer $$$c$$$ ($$$2 \le c \le 10^9$$$).

Output

For each test case, output one integer — the maximum possible value of $$$\text{lcm}(a, b)$$$.

Example
Input
4
4
6
9
114514
Output
3
5
20
3278364045