Bit Equation

Vitaliy is a very lazy student. Attending lectures, especially those that aren't particularly interesting and are scheduled early in the morning, is a rare event for him. Once again, he missed a lecture on discrete mathematics. This time, the topic was bitwise operations, specifically the OR operation.

To assess the students' understanding of the material, the lecturer presented them with an equation of the form:

a OR b = c

Vitaliy solved it quickly. Can you solve it too?

Input

The first line contains the number of equations t (1 ≤ t ≤ 100). Each of the following t lines contains a single number c (1 ≤ c ≤ 2^63 - 1).

Output

For each equation, determine the number of natural numbers a and b such that a ≤ b and a OR b = c for the given c.

Examples