Chika has recently decided to learn more about binary. She decides that numbers are nice when they, when written in binary, have a count of ones that is divisible by 3. Consequently, 7 is the smallest positive integer that Chika considers nice.

She wants to know, for several ~N~, how many positive integers less than or equal are nice. Help her!

Constraints

~1 \le T \le 10^4~

~1 \le N \le 10^{16}~

Input Specification

The first line contains a single positive integer, ~T~.

Each of the next ~T~ lines contains a single positive integer, ~N~.

Output Specification

Output ~T~ lines. On the ~i~th line, output the answer for the given value of ~N~.

Sample Input

1
7

Sample Output

1