[RC-05] 迷失自我

[广告](http://119.27.163.117/problem/86)

对于两个只包含 $7,9$ 的数字串 $S,T$，如果： - $S,T$ 长度均为 $n$； - $S$ 的字典序小于 $T$； - 对于任意 $[l_1,r_1]$ 和 $[l_2,r_2]$（$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，$l_1,r_1,l_2,r_2$ 为整数，两个区间不相同），设 $A_S$ 为将 $S$ 的第 $l_1\sim r_1$ 个字符顺次排列得到的十进制数，$A_T$ 为将 $T$ 的第 $l_1\sim r_1$ 个字符顺次排列得到的十进制数，$B_S$ 为将 $S$ 的第 $l_2\sim r_2$ 个字符顺次排列得到的十进制数，$B_T$ 为将 $T$ 的第 $l_2\sim r_2$ 个字符顺次排列得到的十进制数，有 $\gcd(A_S,B_S)=\gcd(A_T,B_T)$。 那么，就称 $(S,T)$ 是无法辨识的一对。比如，$S=7977$ 和 $T=7979$ 不是无法辨识的，因为取 $[l_1,r_1]=[1,4]$，$[l_2,r_2]=[2,2]$，则 $\gcd(A_S,B_S)=\gcd(7977,9)=3$，$\gcd(A_T,B_T)=\gcd(7979,9)=1$，有 $3\ne 1$。 求长度为 $n$ 的只含 $7,9$ 的数字串中有几对无法辨识。你只需求出答案对 $998244353$ 取模的值。

**本题单个测试点内有多组数据。** 第一行是一个整数，为数据组数 $T$。 接下来一行，每行一个整数，为询问的 $n$。

$T$ 行，每行一个整数，为这组数据的答案对 $998244353$ 取模的值。

1
1

1

对于所有数据，$1\le T\le 10^4$，$1\le n\le 10^{18}$。 详细数据范围如下表： | 测试点编号 | $n$ | $T$ | 分数 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le 10$ | $\le 10$ | $2$ | | $2$ | $\le 10^{18}$ | $\le 10^4$ | $98$ |