异或三角 ### 题目描述 给定 $T$ 个数 $n_1, n_2, \cdots , n_T$，对每个 $n_i$ 请求出有多少组 $a$, $b$, $c$ 满足： 1. $1 ≤ a, b, c ≤ n_i$； 2. $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示二进制按位异或； 3. 长度为 $a, b, c$ 的三条边能组成一个三角形。 ### 输入描述 输入的第一行包含一个整数 $T$。 接下来 $T$ 行每行一个整数，分别表示 $n_1, n_2, \cdots , n_T$。 ### 输出描述 输出 $T$ 行，每行包含一个整数，表示对应的答案。 ### 输入输出样例 #### 示例 >输入 ```txt 2 6 114514 ``` >输出 ```txt 6 11223848130 ``` ### 评测用例规模与约定 对于 $10$% 的评测用例，$T = 1, 1 ≤ n_i ≤ 200$； 对于 $20$% 的评测用例，$T = 1, 1 ≤ n_i ≤ 2000$； 对于 $50$% 的评测用例，$T = 1, 1 ≤ n_i ≤ 2^{20}$； 对于 $60$% 的评测用例，$1 ≤ T ≤ 100000, 1 ≤ n_i ≤ 2^{20}$； 对于所有评测用例，$1 ≤ T ≤ 100000, 1 ≤ n_i ≤ 2^{30}$。