Roundgod 即將參加高考（普通高等學校招生全國統一考試），他夢想中的學校是浙江大學。他在學習數學時看到一道有趣的題目，這道題目與帕斯卡三角形有關。

帕斯卡三角形的定義如下：

帕斯卡三角形每一列的第一個元素和最後一個元素都是 $1$，而第 $n$ 列的第 $m$ 個元素等於第 $n-1$ 列的第 $m$ 個元素與第 $m-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