题目描述

给定 $T$ 个数 $n_1, n_2, …… , 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$ 行，每行包含一个整数，表示对应的答案。

2
6
114514

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}$。