P7817 [RC-05] Lost Self

[Advertisement](http://119.27.163.117/problem/86)

For two digit strings $S, T$ consisting only of $7,9$, if: - The lengths of $S, T$ are both $n$. - The lexicographical order of $S$ is smaller than $T$. - For any $[l_1, r_1]$ and $[l_2, r_2]$ ($1 \le l_1 \le r_1 \le n$, $1 \le l_2 \le r_2 \le n$, where $l_1, r_1, l_2, r_2$ are integers, and the two intervals are different), let $A_S$ be the decimal number formed by arranging the characters of $S$ from position $l_1$ to $r_1$ in order, $A_T$ be the decimal number formed by arranging the characters of $T$ from position $l_1$ to $r_1$ in order, $B_S$ be the decimal number formed by arranging the characters of $S$ from position $l_2$ to $r_2$ in order, and $B_T$ be the decimal number formed by arranging the characters of $T$ from position $l_2$ to $r_2$ in order. Then $\gcd(A_S, B_S) = \gcd(A_T, B_T)$. Then $(S, T)$ is called an indistinguishable pair. For example, $S = 7977$ and $T = 7979$ are not an indistinguishable pair, because taking $[l_1, r_1] = [1, 4]$ and $[l_2, r_2] = [2, 2]$, we have $\gcd(A_S, B_S) = \gcd(7977, 9) = 3$ and $\gcd(A_T, B_T) = \gcd(7979, 9) = 1$, so $3 \ne 1$. Find how many indistinguishable pairs there are among length $n$ digit strings consisting only of $7,9$. You only need to output the answer modulo $998244353$.

**This problem has multiple test cases within a single test point.** The first line contains an integer $T$, the number of test cases. Each of the next $T$ lines contains one integer $n$, the query.

Output $T$ lines, each containing one integer: the answer for that test case modulo $998244353$.

For all testdata, $1 \le T \le 10^4$, $1 \le n \le 10^{18}$. The detailed Constraints are as follows: | Test Point ID | $n$ | $T$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $\le 10$ | $\le 10$ | $2$ | | $2$ | $\le 10^{18}$ | $\le 10^4$ | $98$ | Translated by ChatGPT 5