Define a function \(g\) by

• \(g(1)=1\) and \(g(3)=3\);
• \(g(2n)=g(n)\);
• \(g(4n+1)=2g(2n+1)-g(n)\);
• \(g(4n+3)=3g(2n+1)-2g(n)\).

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

Input

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

The input satisfies:

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

Output

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

Example

Input

3
1
2
7

Output

1
1
7

Explanation

The base and recurrence rules give g(1)=1, g(2)=g(1)=1, and the displayed value for g(7).