13481348 SUSTech Online Judge
Problem 1348 --[Medium] Magic Recurrence

1348: [Medium] Magic Recurrence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 601  Solved: 239
[Submit][Status][Web Board]

Description

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)\).

Input

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

Output an integer \(ans\) in one line for each test case, representing the output of \(f\).

Sample Input

3
10
20
30

Sample Output

11
29
53

HINT

Source

 

[Submit][Status]