题目描述

给定 $T$ 个数 $n_{1}, n_{2}, \cdots, n_{T}$, 对每个 $n_{i}$ 请求出有多少组 $a, b, c$ 满足:

1. $1 \leq a, b, c \leq 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 \leq n_{i} \leq 200$; 对于 $20 \%$ 的评测用例, $T=1,1 \leq n_{i} \leq 2000$ ；

对于 $50 \%$ 的评测用例, $T=1,1 \leq n_{i} \leq 2^{20}$;

对于 $60 \%$ 的评测用例, $1 \leq T \leq 100000,1 \leq n_{i} \leq 2^{20}$;

对于所有评测用例, $1 \leq T \leq 100000,1 \leq n_{i} \leq 2^{30}$ 。

蓝桥杯 2021 国赛 A 组 I 题（B 组 J 题）。