Problem E: [Medium] Magic Recurrence

Problem E: [Medium] Magic Recurrence

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 606  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

[Submit][Status]