Roundgod akan mengikuti Gaokao (Ujian Nasional Terpadu untuk Penerimaan di Universitas dan Perguruan Tinggi Umum), dan sekolah impiannya adalah Zhejiang University. Saat belajar Matematika, ia menemukan sebuah soal menarik yang berkaitan dengan Segitiga Pascal.

Definisi Segitiga Pascal diberikan di bawah ini:

Elemen pertama dan elemen terakhir pada setiap baris Segitiga Pascal adalah $1$, dan elemen ke-$m$ pada baris ke-$n$ sama dengan jumlah elemen ke-$m$ dan ke-$(m-1)$ pada baris ke-$(n-1)$. Berikut adalah contoh Segitiga Pascal dengan 5 tingkat.

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

Dalam soal tersebut, Roundgod diminta menghitung berapa banyak elemen pada baris ke-126 Segitiga Pascal yang merupakan bilangan ganjil.

Setelah menyelesaikannya, Roundgod memikirkan versi yang lebih sulit dari soal ini. Ia memberimu banyak permintaan mengenai pertanyaan serupa, tetapi dengan nomor baris yang lebih besar. Hitunglah berapa banyak elemen pada baris ke-$k$ Segitiga Pascal yang merupakan bilangan ganjil.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1\le T\le 500$), yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama dan satu-satunya berisi sebuah bilangan bulat $K$ ($K\le 10^{18}$), yang menyatakan nomor baris Segitiga Pascal yang diminta.

Keluaran

Untuk setiap kasus uji, keluarkan banyaknya bilangan ganjil pada baris ke-$k$.

Contoh

Masukan 1

3
3
4
5

Keluaran 1

2
4
2