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