Description

给定一个整数 $n$，请找出从 $1$ 到 $n-1$ 中所有与 $n$ 互质的整数所组成的列表的中位数。

回忆一下，如果两个整数 $a$ 和 $b$ 的最大公约数为 $1$，则称它们是互质的。列表 $L$ 的中位数定义为：若 $|L|$ 为偶数，则为第 $\frac{|L|}{2}$ 个元素；若 $|L|$ 为奇数，则为第 $\frac{|L|+1}{2}$ 个元素。这里 $L$ 假定为升序排列，$|L|$ 表示 $L$ 的长度，且下标从 $1$ 开始。

Input Format

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。

接下来的每组测试用例包含一行，一个整数 $n$（$2 \le n \le 10^{18}$）。

Output Format

对于每组测试用例，输出一个整数，表示从 $1$ 到 $n-1$ 中所有与 $n$ 互质的整数所组成的列表的中位数。

3
6
10
19

1
3
9

Hint

由 ChatGPT 4.1 翻译