P8766 [Lanqiao Cup 2021 National AB] XOR Triangle

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.

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

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

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