整个楼梯共 $3^N$ 级台阶。
HG 刷漆的规律是：对于**从上到下**第 $I$ 级台阶，若 $V_3(I)$ 是奇数，则刷在左边，否则刷在右边。**$V_3(I)$ 的定义请见提示。**
小 Y 因为强迫症，要求自己不能踩到油漆。
现在他来求助你，他最少会踩到油漆多少次？
- 一次只能下一级台阶。
- 如果小 Y 站在当前台阶的左边，则他必须站在下一级台阶的右边，反之亦然。
- 如果油漆在当前台阶左边，那么需要站在当前台阶右边才算没踩到油漆，反之亦然。
- 小 Y 唯一可以控制的是：他在第 $1$ 级台阶上站在哪边。也就是说，小 Y 只有 $2$ 种下楼梯的方案供选择。
答案对 $10^9+7$ 取模。
### 形式化题意
给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。
其中：
- $A=\texttt{101010101\ldots101}$；
- $B=\texttt{010101010\ldots010}$；
- $C=\texttt{001001000\ldots}$；具体来说，第 $I$ 个字符为 $V_3(I) \bmod 2$。**$V_3(I)$ 的定义请见提示。**
记 $\operatorname{mc}(X,Y)$ 为字符串 $X$ 和 $Y$ 中匹配的字符的个数。
试求：
$$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$$
答案对 $10^9+7$ 取模。
## Input
**本题有多组数据。**
第一行，一个正整数 $T$，代表数据组数。
下面 $T$ 行，每行一个正整数 $N$。
## Output
每组数据一行，输出踩到油漆的最少次数，即 $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$。
**答案对 $10^9+7$ 取模。**
[samples]
## Background
小 Y 是一个胖子，他最爱下楼梯了，因为下楼梯很省力气，但是他却有强迫症。
由于刷漆工人 HG 的油漆不够，每一层台阶都只刷了一半——左边或右边，好让小 Y 下楼时不踩到油漆。（~~众人：这是什么逻辑？~~）
## Note
样例 $1$ 解释：
- $A=\texttt{101}$；
- $B=\texttt{010}$；
- $C=\texttt{001}$；
- $\operatorname{mc}(A,C)=2$；
- $\operatorname{mc}(B,C)=1$；
- $\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}=1$。
------------
| 测试点编号 | $T \le$ | $N \le$ | 分值 |
| :-: | :-: | :-: | :-: |
| $1$ | $10$ | $10$ | $50$ |
| $2$ | $10^5$ | $10^{18}$ | $50$ |
对于 $100\%$ 的数据，$1 \le T \le 10^{5}$，$1 \le N \le 10^{18}$。
> **提示：** $V_3(X)$ 指 $X$ 中质因数 $3$ 的个数。例如，$V_3(14)=0$，$V_3(18)=2$。