F. Nice (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A number is nice if it contains only the digits $$$6$$$ and $$$9$$$. For example, $$$6$$$, $$$99$$$ and $$$69$$$ are nice numbers but $$$5$$$, $$$63$$$ and $$$169$$$ are not.

Let $$$f(m)$$$ be the number of nice numbers from $$$1$$$ to $$$m$$$.

You are given a digit string $$$s$$$ of length $$$n$$$ consisting of digits from $$$1$$$ to $$$9$$$. Let $$$s[l \ldots r]$$$ be the substring of $$$s$$$ from index $$$l$$$ to $$$r$$$ and $$$f(s[l \ldots r])$$$ be the number of nice numbers from $$$1$$$ to $$$m$$$ where $$$m$$$ is the decimal number represented by the digits of the substring $$$s[l \ldots r]$$$.

Your task is to find the sum, modulo $$$998\,244\,353$$$, of $$$f(s[l \dots r])$$$ over all $$$1 \leq l \leq r \leq n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{5}$$$) — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^{6}$$$), representing the length of the string.

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of digits from $$$1$$$ to $$$9$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.

Output

For each test case, print a single integer — the answer to the problem.

Example
Input
3
2
69
3
123
10
1692967321
Output
7
10
4586
Note

In the first test case,

$$$f(s[1 \ldots 1]) = f(6) = |\{6\}|= 1$$$,

$$$f(s[2 \ldots 2]) = f(9) = |\{6, 9\}|= 2$$$,

$$$f(s[1 \ldots 2]) = f(69) = |\{6, 9, 66, 69\}|= 4$$$,

So the answer is $$$1 + 2 + 4 = 7$$$