Roundgod wird bald am Gaokao (der landesweiten einheitlichen Aufnahmeprüfung für allgemeine Universitäten und Hochschulen) teilnehmen, und seine Wunschuniversität ist die Zhejiang University. Beim Mathematiklernen stößt er auf eine interessante Aufgabe zum Pascalschen Dreieck.

Das Pascalsche Dreieck ist wie folgt definiert:

Das erste und das letzte Element jeder Zeile des Pascalschen Dreiecks sind $1$, und das $m$-te Element der $n$-ten Zeile ist die Summe des $m$-ten und des $(m-1)$-ten Elements der $(n-1)$-ten Zeile. Hier ist ein Beispiel eines Pascalschen Dreiecks mit $5$ Zeilen:

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

In der Aufgabe soll Roundgod berechnen, wie viele Elemente in der $126$-ten Zeile des Pascalschen Dreiecks ungerade sind.

Nachdem er die Aufgabe gelöst hat, denkt sich Roundgod eine schwierigere Variante aus. Er stellt dir viele ähnliche Fragen, doch die Zeilennummern sind größer. Berechne bitte, wie viele Elemente in der $k$-ten Zeile des Pascalschen Dreiecks ungerade sind.

Eingabe

Es gibt mehrere Testfälle. Die erste Eingabezeile enthält eine ganze Zahl $T$ ($1 \le T \le 500$), die Anzahl der Testfälle. Für jeden Testfall gilt:

Die erste und einzige Zeile enthält eine ganze Zahl $K$ ($K \le 10^{18}$), die die gesuchte Zeilennummer im Pascalschen Dreieck angibt.

Ausgabe

Gib für jeden Testfall die Anzahl der ungeraden Zahlen in der $k$-ten Zeile aus.

Beispiele

Eingabe 1

3
3
4
5

Ausgabe 1

2
4
2