J. Asem hates Coprimes (Green)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Asem recently learned about coprime numbers and immediately started hating them.

Given an integer $$$N$$$, Asem wants to find the largest integer $$$M$$$ such that $$$1 \le M \lt N$$$ and $$$M$$$ is NOT coprime with $$$N$$$.

Two integers are said to be coprime if their greatest common divisor is equal to $$$1$$$.

Help Asem find the answer.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ – the number of test cases.

Each test case consists of a single integer $$$N$$$ $$$(2 \le N \le 10^6)$$$.

Output

For each test case, print a single integer – the maximum integer $$$M$$$ such that $$$1 \le M \lt N$$$ and $$$\gcd(M, N) \gt 1$$$.

If no such integer exists, print $$$-1$$$.

Example
Input
3
2
3
6
Output
-1
-1
4