Median of the Coprime Sequence

Problem Description

Given a positive integer $N$, consider the sequence formed by all integers in $1 \sim N-1$ that are coprime to $N$. Find the median of this sequence.

We define the median of a sequence of length $K$ to be the element at position $\lfloor (K+1)/2 \rfloor$ (1-indexed) when the sequence is sorted in ascending order. Two positive integers $a$ and $b$ are coprime if and only if $\gcd(a, b) = 1$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the input contains one positive integer $N$.

For all test cases, $1 \le T \le 100$, $2 \le N \le 10^{18}$.

Output Format

For each test case, output one line containing a single positive integer: the answer.

Sample Input

3
6
10
19

Sample Output

1
3
9