Roundgod está a punto de presentarse al Gaokao (Examen Nacional Unificado de Admisión a Universidades y Centros de Educación Superior), y la universidad de sus sueños es Zhejiang University. Mientras estudia matemáticas, encuentra un problema interesante relacionado con el triángulo de Pascal.

La definición del triángulo de Pascal es la siguiente:

El primer y el último elemento de cada fila del triángulo de Pascal son $1$, y el elemento $m$ de la fila $n$ es igual a la suma de los elementos $m$ y $m-1$ de la fila $n-1$. Este es un ejemplo de un triángulo de Pascal de 5 niveles.

$$ \begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1 \end{array} $$

En el problema, Roundgod debe calcular cuántos elementos de la fila $126$ del triángulo de Pascal son números impares.

Después de resolverlo, Roundgod piensa en una versión más difícil. Te plantea muchas consultas similares, pero con un número de fila mayor. Calcula cuántos elementos de la fila $k$ del triángulo de Pascal son números impares.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ ($1\le T\le500$), que indica el número de casos de prueba. Para cada caso:

La primera y única línea contiene un entero $K$ ($K\le10^{18}$), que indica el número de fila solicitado del triángulo de Pascal.

Salida

Para cada caso de prueba, imprime el número de números impares de la fila $k$.

Ejemplos

Entrada 1

3
3
4
5

Salida 1

2
4
2