题目描述
给定正整数$N$, 求出 $1 \sim N - 1$中所有与$N$互质的数构成的序列 的中位数.
我们定义 : 一个长度为$K$的序列的中位数是序列中第$\lfloor\frac{K + 1}{2}\rfloor$大的数字. 且两个正整数$a$ 与 $b$ 互质当且仅当 $gcd(a, b) = 1$.
输入格式
第一行一个正整数$T$, 表示数据组数.
对于每组数据, 一行输入一个正整数$N$.
对于所有数据, 满足$1 \leq T \leq 100$, $2 \leq N \leq 10^{18} $.
输出格式
对于每组测试数据, 输出一行一个正整数, 表示答案.
样例输入
3
6
10
19
样例输出
1
3
9