Find largest non-negative number less than or equal to floor (N/2) which is coprime to N.

Two number a and b are considered to coprime if gcd (a, b) = 1.

Input

T : number of test  cases (T <= 1000)

For next T lines, every line contains n >= 1 && n <= 10^12;

Output

For each test case, output as described in the problem statement.

Example

Input:
4
3
4
5
100 

Output:
1
1
2
49