对于每个非负整数 $n$，定义 $n_2$ 为 $n$ 的二进制表示，并在其左侧补上无穷多个前导零。对于每个整数 $n \ge 0$，我们将 $n_2$ 写在新的一行上。现在我们得到一个如下所示的无限棋盘：

$$ \begin{array}{ccccccccc} \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \dots & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \dots & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ \dots & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \dots & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ \dots & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \dots & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{array} $$

设 $f$ 为这样一个函数：$f(n)$ 是一个数，其第 $k$ 位等于 $n+k$ 的第 $k$ 位，对于所有 $k \ge 0$ 均成立。例如，$f(0) = 0$ 且 $f(3) = 5$。换句话说，如果我们顺时针旋转棋盘 $45^\circ$，那么 $f(n)$ 的二进制表示将写在第 $n$ 行上（如果第 $0$ 行以右上角的 $0$ 结尾）。

$$ \begin{array}{ccccccccc} & & & \dots & & & & & \\ \dots & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \leftarrow f(0) \\ \dots & 0 & 0 & 0 & 0 & 0 & 1 & 1 & \leftarrow f(1) \\ \dots & 0 & 0 & 0 & 1 & 1 & 0 & & \leftarrow f(2) \\ \dots & 0 & 0 & 1 & 0 & 1 & & & \leftarrow f(3) \\ \dots & 0 & 1 & 0 & 0 & & & & \leftarrow f(4) \\ & & & \dots & & & & & \end{array} $$

设 $g(k)$ 为不在序列 $f(0), f(1), f(2), \dots$ 中出现的第 $k$ 个非负整数。你的任务是求出 $g(k)$ 并将其对 $10^9 + 7$ 取模。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 接下来的 $t$ 行，每行包含一个整数 $k$ ($1 \le k \le 10^{18}$)，表示一个测试用例。

输出格式

输出 $t$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

样例

输入 1

5
1
2
3
4
5

输出 1

1
2
7
12
29