There is a magic recurrence function \(f\), defined as
\[
f(n) = \begin{cases}
1, (n\leq 3) \\
f(\lfloor \frac{n}{2}\rfloor -1)+f(\lfloor \frac{n}{2}\rfloor)+f(\lfloor \frac{n}{2}\rfloor +1), (n\geq 4)
\end{cases}
\]
where \(\lfloor a\rfloor\) denotes the answer to round down \(a\) to an integer.
Given the input \(n\), please calculate \(f(n)\).
The first line contains an integer \(T(1\leq T\leq 10^3)\), representing the number of test cases.
Then \(T\) lines follow. Each line contains an integer \(n (1\leq 10^6)\) as the input of the function \(f\) for a test case.
Output an integer \(ans\) in one line for each test case, representing the output of \(f\).