Description

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$.

Input Format

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 Format

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

1
1

1

Hint

For all testdata, $1 \le T \le 10^4$, $1 \le n \le 10^{18}$.

The detailed Constraints are as follows:

Translated by ChatGPT 5