Roundgod 就快要參加高考（普通高等學校招生全國統一考試），而佢夢想入讀嘅學校係 Zhejiang University。佢溫習數學嗰陣見到一道有趣嘅題目，題目同帕斯卡三角形有關。

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

帕斯卡三角形每一行嘅第一個同最後一個元素都係 $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