Roundgod sắp tham dự Gaokao (Kỳ thi tuyển sinh thống nhất toàn quốc vào các trường đại học và cao đẳng), và ngôi trường mơ ước của cậu là Zhejiang University. Trong khi học Toán, cậu gặp một bài toán thú vị liên quan đến tam giác Pascal.

Định nghĩa tam giác Pascal được cho dưới đây:

Phần tử đầu tiên và phần tử cuối cùng của mỗi hàng trong tam giác Pascal đều bằng $1$, và phần tử thứ $m$ của hàng thứ $n$ bằng tổng của phần tử thứ $m$ và phần tử thứ $m-1$ của hàng thứ $n-1$. Dưới đây là một ví dụ về tam giác Pascal có $5$ tầng.

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

Trong bài toán đó, Roundgod được yêu cầu tính xem có bao nhiêu phần tử ở hàng thứ $126$ của tam giác Pascal là số lẻ.

Sau khi giải được bài toán, Roundgod nghĩ ra một phiên bản khó hơn. Cậu đưa cho bạn nhiều yêu cầu về những câu hỏi tương tự, nhưng số thứ tự hàng sẽ lớn hơn. Hãy tính xem có bao nhiêu phần tử ở hàng thứ $k$ của tam giác Pascal là số lẻ.

Dữ liệu vào

Có nhiều trường hợp kiểm thử. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1\le T\le 500$), cho biết số trường hợp kiểm thử. Với mỗi trường hợp kiểm thử:

Dòng đầu tiên và duy nhất chứa một số nguyên $K$ ($K\le 10^{18}$), cho biết số thứ tự hàng cần xét trong tam giác Pascal.

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in ra số lượng số lẻ trong hàng thứ $k$.

Ví dụ

Dữ liệu vào 1

3
3
4
5

Dữ liệu ra 1

2
4
2