给定一个整数 $n$，求所有 $1$ 到 $n-1$ 之间与 $n$ 互质的整数构成的列表的中位数。
回想一下，如果两个整数 $a$ 和 $b$ 的最大公约数为 $1$，则称它们互质。列表 $L$ 的中位数定义为：若 $|L|$ 为偶数，则为 $L$ 中第 $\frac{|L|}{2}$ 个元素；若 $|L|$ 为奇数，则为 $L$ 中第 $\frac{|L|+1}{2}$ 个元素。此处假设 $L$ 已按升序排列，$|L|$ 表示 $L$ 的长度，且索引从 $1$ 开始。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^3$)。
接下来是各测试用例的描述。
每个测试用例仅包含一行，为一个整数 $n$ ($2 \le n \le 10^{18}$)。
输出格式
对于每个测试用例，输出一个整数，即 $1$ 到 $n-1$ 之间与 $n$ 互质的整数列表的中位数。
样例
样例输入 1
3 6 10 19
样例输出 1
1 3 9