Roundgod はまもなく Gaokao（普通大学への入学のための全国統一試験）を受験し、志望校は 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