背景

广告

题目描述

对于两个只包含 $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}$。

详细数据范围如下表：