+⊕3\%#13090
You are given a non-negative integer . Consider all triples of non-negative integers (a,b,c) satisfying both of the following:
a+b+c=x;
(a \oplus b \oplus c) \bmod 3 = 0, where denotes the bitwise exclusive-or operation.
Among all such triples, find the maximum possible value of the product a \cdot b \cdot c.
It can be shown that for every x \geq 2 at least one valid triple exists.
The first line contains a single integer (1 \leq t \leq 10^5) — the number of test cases.
Each test case contains a single integer (2 \leq x \leq 10^6).
It is not guaranteed that \sum x \le 10^6 overall tests.
For each test case, output a single integer — the maximum value of a \cdot b \cdot c over all valid triples.
Note: the answer may be as large as roughly 10^{18}, which does not fit into a 32-bit integer type. Use 64-bit integers.
Example 1
Subtask ( points) : (\sum x \leq 100).
Subtask ( points) : (\sum x \leq 2000).
Subtask ( points) : No additional constraints.