Roundgod 即将参加高考，他的目标院校是浙江大学。在学习数学时，他发现了一个与杨辉三角（Pascal's Triangle）有关的有趣问题。

杨辉三角的定义如下： 杨辉三角中每一行的第一个元素和最后一个元素均为 1，第 $n$ 行的第 $m$ 个元素等于第 $n-1$ 行的第 $m$ 个元素与第 $m-1$ 个元素之和。以下是一个 5 层杨辉三角的示例：

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

在这个任务中，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