Problem Description

Given $T$ numbers $n_{1}, n_{2}, \cdots, n_{T}$, for each $n_{i}$, find how many triples $a, b, c$ satisfy:

1. $1 \leq a, b, c \leq n_{i}$;

2. $a \oplus b \oplus c = 0$, where $\oplus$ denotes bitwise XOR in binary;

3. The three sides with lengths $a, b, c$ can form a triangle.

Input Format

The first line contains an integer $T$.

The next $T$ lines each contain an integer, representing $n_{1}, n_{2}, \cdots, n_{T}$.

Output Format

Output $T$ lines, each containing an integer, representing the corresponding answer.

2
6
114514

6
11223848130

Hint

For $10\%$ of the testdata, $T = 1$, $1 \leq n_{i} \leq 200$.

For $20\%$ of the testdata, $T = 1$, $1 \leq n_{i} \leq 2000$.

For $50\%$ of the testdata, $T = 1$, $1 \leq n_{i} \leq 2^{20}$.

For $60\%$ of the testdata, $1 \leq T \leq 100000$, $1 \leq n_{i} \leq 2^{20}$.

For all testdata, $1 \leq T \leq 100000$, $1 \leq n_{i} \leq 2^{30}$.

Lanqiao Cup 2021 National Contest, Group A Problem I (Group B Problem J).

Translated by ChatGPT 5