题目描述

给定正整数$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