Define a sequence \(f\) by \(f(0)=0\), \(f(1)=1\), and \(f(2)=2\). For \(k>0\),

• \(f(3k)=f(2k)\);
• \(f(3k+1)=f(2k)+f(2k+1)\);
• \(f(3k+2)=f(2k)+f(2k+1)+f(2k+2)\).

Answer \(Q\) queries for \(f(n)\).

Input

The first line contains \(Q\). Each of the next \(Q\) lines contains \(n\).

The input satisfies:

• \(1 \le Q \le 20\)
• \(0 \le n \le 2 \times 10^9\)

Output

For each query, print \(f(n)\) on its own line.

Example

Input

3
0
4
8

Output

0
4
16

Explanation

Applying the three recurrence branches to queries 0, 4, and 8 produces the three displayed values.