Roundgod wkrótce przystąpi do Gaokao (Ogólnokrajowego Jednolitego Egzaminu Wstępnego na Uczelnie Wyższe), a jego wymarzoną uczelnią jest Zhejiang University. Podczas nauki matematyki trafia na ciekawe zadanie związane z trójkątem Pascala.

Definicja trójkąta Pascala jest następująca:

Pierwszy i ostatni element każdego wiersza trójkąta Pascala to $1$, a $m$-ty element $n$-tego wiersza jest równy sumie $m$-tego i $(m-1)$-szego elementu $(n-1)$-szego wiersza. Oto przykład trójkąta Pascala o 5 poziomach.

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

W zadaniu Roundgod musi obliczyć, ile elementów w $126$-tym wierszu trójkąta Pascala jest liczbami nieparzystymi.

Po jego rozwiązaniu Roundgod wymyśla trudniejszą wersję tego zadania. Podaje ci wiele podobnych pytań, lecz z większym numerem wiersza. Oblicz, ile elementów w $k$-tym wierszu trójkąta Pascala jest liczbami nieparzystymi.

Wejście

Danych jest wiele przypadków testowych. Pierwszy wiersz wejścia zawiera liczbę całkowitą $T$ ($1\le T\le500$), oznaczającą liczbę przypadków testowych. Dla każdego przypadku testowego:

Pierwszy i jedyny wiersz zawiera liczbę całkowitą $K$ ($K\le10^{18}$), oznaczającą żądany numer wiersza w trójkącie Pascala.

Wyjście

Dla każdego przypadku testowego wypisz liczbę liczb nieparzystych w $k$-tym wierszu.

Przykład

Wejście 1

3
3
4
5

Wyjście 1

2
4
2