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¹²).

Output

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

Example

Input:
4
3
4
5
100 

Output:
1
1
2
49