给定 $T$ 个数 $n_1,n_2,\cdots,n_T$，对每个 $n_i$ 请求出有多少组 $a,b,c$ 满足： 1. $1 \le a,b,c \le n_i$ 2. $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示二进制按位异或 3. 长度为 $a,b,c$ 的三条边能组成一个三角形

输入的第一行包含一个整数 $T$. 接下来 $T$ 行每行一个整数，分别表示 $n_1,n_2,\cdots,n_T$. - 对于 $10\%$ 的评测用例，$T=1,\ 1 \le n_i \le 200$. - 对于 $20\%$ 的评测用例，$T=1,\ 1 \le n_i \le 2000$. - 对于 $50\%$ 的评测用例，$T=1,\ 1 \le n_i \le 2^{20}$. - 对于 $60\%$ 的评测用例，$1 \le T \le 100000,\ 1 \le n_i \le 2^{20}$. - 对于所有评测用例，$1 \le T \le 100000,\ 1 \le n_i \le 2^{30}$.

输出 $T$ 行，每行包含一个整数，表示对应的答案。

第十二届蓝桥杯大赛软件类国赛C/C++大学B组