Roundgod незабаром складатиме Gaokao (загальнонаціональний єдиний іспит для вступу до звичайних університетів і коледжів), а університет його мрії — Zhejiang University. Вивчаючи математику, він натрапив на цікаву задачу, пов'язану з трикутником Паскаля.

Означення трикутника Паскаля наведено нижче:

Перший і останній елементи кожного рядка трикутника Паскаля дорівнюють $1$, а $m$-й елемент $n$-го рядка дорівнює сумі $m$-го та $(m-1)$-го елементів $(n-1)$-го рядка. Ось приклад трикутника Паскаля з 5 рівнями.

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

У задачі Roundgod має обчислити, скільки елементів $126$-го рядка трикутника Паскаля є непарними числами.

Розв'язавши її, Roundgod придумав складнішу версію цієї задачі. Він дає вам багато запитів із подібними питаннями, але номер рядка буде більшим. Обчисліть, скільки елементів $k$-го рядка трикутника Паскаля є непарними числами.

Вхідні дані

Є декілька тестових випадків. Перший рядок вхідних даних містить ціле число $T$ ($1\le T\le500$) — кількість тестових випадків. Для кожного тестового випадку:

Перший і єдиний рядок містить ціле число $K$ ($K\le10^{18}$) — потрібний номер рядка трикутника Паскаля.

Вихідні дані

Для кожного тестового випадку виведіть кількість непарних чисел у $k$-му рядку.

Приклади

Вхідні дані 1

3
3
4
5

Вихідні дані 1

2
4
2