U175972 「dWoi R2」Elevator 加强版

# 请注意输入输出格式与数据范围 若数据有误请私信。

现有正整数 $a,b,c$ 满足 $\alpha$ 式：$\dfrac{1}{a}-\dfrac{1}{b}=\dfrac{1}{c}$，且 $\gcd (a,b,c)=1$。 现给定正整数 $N$，请编程求出满足 $c \leq N$ 的 $\alpha$ 式的个数以及满足以下条件的一个 $b$： 对所有 $c=N$ 得到的 $\alpha$ 式中使得 $a$ 最小。 请对所有不大于 $ n $ 的数求出这两问的答案。

第一行一个数 $ T $。 接下来 $ T $ 行，第 $ k $ 行有一个数 $ n_k $。

$ T $ 个 64 位无符号整形数。 设 $ ans1_i $ 是对于 $ c=i $ 时第一问的答案， $ ans2_i $ 同理。 第 $ k $ 行的结果为 $ \oplus_{i=2}^{n_k} (ans1_i + ans2_i) $。

对于 $ 100\% $ 的数据，满足 $ T = 10^5,1 \leq n \leq 10^7 $。 若 $ n=1 $，请输出 $ 0 $。