Roundgod s’apprête à passer le Gaokao (examen national unifié d’admission dans les universités et établissements d’enseignement supérieur) et l’établissement de ses rêves est Zhejiang University. En étudiant les mathématiques, il découvre un problème intéressant lié au triangle de Pascal.

La définition du triangle de Pascal est donnée ci-dessous :

Le premier et le dernier élément de chaque ligne du triangle de Pascal valent $1$, et le $m$-ième élément de la $n$-ième ligne est égal à la somme des $m$-ième et $(m-1)$-ième éléments de la $(n-1)$-ième ligne. Voici un exemple de triangle de Pascal à 5 niveaux.

$$ \begin{gathered} 1\\ 1\quad1\\ 1\quad2\quad1\\ 1\quad3\quad3\quad1\\ 1\quad4\quad6\quad4\quad1 \end{gathered} $$

Dans ce problème, Roundgod doit calculer combien d’éléments de la $126$-ième ligne du triangle de Pascal sont des nombres impairs.

Après l’avoir résolu, Roundgod imagine une version plus difficile de ce problème. Il vous soumet de nombreuses questions similaires, mais avec des numéros de ligne plus grands. Calculez combien d’éléments de la $k$-ième ligne du triangle de Pascal sont des nombres impairs.

Entrée

Il y a plusieurs cas de test. La première ligne de l’entrée contient un entier $T$ ($1\le T\le 500$), indiquant le nombre de cas de test. Pour chaque cas de test :

La première et unique ligne contient un entier $K$ ($K\le 10^{18}$), indiquant le numéro de ligne demandé dans le triangle de Pascal.

Sortie

Pour chaque cas de test, affichez le nombre de nombres impairs dans la $k$-ième ligne.

Exemples

Entrée 1

3
3
4
5

Sortie 1

2
4
2