Triangle Triples with XOR Condition

Given \(T\) test cases. For each test case you are given an integer \(n\). You need to count the number of ordered triples \((a, b, c)\) such that:

1. \(1 \le a, b, c \le n\).
2. \(a \oplus b \oplus c = 0\) where \(\oplus\) denotes the bitwise XOR operator. Note that this implies \(c = a \oplus b\).
3. The three lengths \(a, b, c\) can form a triangle, i.e. they satisfy the triangle inequalities: \(a+b>c\), \(a+c>b\), and \(b+c>a\).

Output the count of such triples for each test case.

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(T\) representing the number of test cases.

Then \(T\) lines follow, each containing one integer \(n\).

Constraints:

• \(1 \le T\)
• \(1 \le n \le 10^3\) (the constraints are assumed to be small enough for a double loop solution)

outputFormat

For each test case, output a single integer representing the number of valid triples \((a, b, c)\) that satisfy the conditions.

sample

3
1
6
10

0
6
8