Roundgod está prestes a fazer o Gaokao (Exame Nacional Unificado de Admissão às Universidades e Instituições de Ensino Superior), e a escola dos seus sonhos é a Zhejiang University. Enquanto estuda Matemática, ele encontra um problema interessante relacionado com o triângulo de Pascal.

A definição do triângulo de Pascal é apresentada a seguir:

O primeiro e o último elemento de cada linha do triângulo de Pascal são iguais a $1$, e o $m$-ésimo elemento da $n$-ésima linha é igual à soma do $m$-ésimo e do $(m-1)$-ésimo elemento da $(n-1)$-ésima linha. Eis um exemplo de um triângulo de Pascal com 5 níveis.

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

Nesse problema, Roundgod deve calcular quantos elementos da $126$-ésima linha do triângulo de Pascal são números ímpares.

Depois de o resolver, Roundgod pensa numa versão mais difícil desse problema. Ele apresenta muitas consultas sobre questões semelhantes, mas com números de linha maiores. Calcule quantos elementos da $k$-ésima linha do triângulo de Pascal são números ímpares.

Entrada

Há vários casos de teste. A primeira linha da entrada contém um inteiro $T$ ($1 \le T \le 500$), que indica o número de casos de teste. Para cada caso de teste:

A primeira e única linha contém um inteiro $K$ ($K \le 10^{18}$), que indica o número da linha pretendida no triângulo de Pascal.

Saída

Para cada caso de teste, apresente o número de números ímpares da $k$-ésima linha.

Exemplos

Entrada 1

3
3
4
5

Saída 1

2
4
2