$$$\text{DAY}^{-1}$$$
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Inspired by a concept from Belmaxii, Clamee formulated the following problem:

You have a string p which is composed of the pattern "xtu" repeated $$$n$$$ times, and another string $$$q$$$ which is made up of lowercase letters. The task is to determine the number of times the string $$$q$$$ appears as a subsequence within the given string $$$p$$$.

A string $$$s$$$ is considered a subsequence of string $$$t$$$ if it can be obtained by removing some (potentially none) characters from $$$t$$$. Subsequences are distinct if a character present at a certain position in $$$t$$$ is excluded in one subsequence but included in another.

Input

Each test is comprised of multiple test cases. The initial line presents an integer $$$T~(1\le T \le 10^5)$$$, which is the tally of test cases.

In each of the subsequent $$$T$$$ lines, you will find an integer $$$n~(1\le n \le 10^{18})$$$, representing the number of repetitions, followed by a string $$$q~(1\le |q| \le 3\cdot n, 1\le \sum |q| \le 10^6)$$$. The string $$$q$$$ consists of lowercase letters.

Output

For each test case, you are to output a single line containing the count of occurrences of the string q, computed modulo $$$998244353$$$.

Example
Input
5
1 t
114514 xtuxtu
3 xtuxt
1919810 utx
19260817 xtc
Output
1
564946452
6
607962364
0
Note

In the third test case, the given string $$$p$$$ is "xtuxtuxtu",the given string $$$q$$$ is "xtuxt" you can choose subsequence following:

xtuxtuxtu

xtuxtuxtu

xtuxtuxtu

xtuxtuxtu

xtuxtuxtu

xtuxtuxtu