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 \le 500$), обозначающее число тестовых примеров. Для каждого тестового примера:

Первая и единственная строка содержит целое число $K$ ($K \le 10^{18}$), обозначающее требуемый номер строки треугольника Паскаля.

Выходные данные

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

Примеры

Входные данные 1

3
3
4
5

Выходные данные 1

2
4
2