<? echo $row['title']." - ".$MSG_PROBLEM."

Time Limit: 2 sec / Memory Limit: 1024 MB

Score :

500

points

Solve the following problem for

T

test cases.
Given an integer

N

and a string

S

, find the number of strings

X

that satisfy all of the conditions below, modulo

998244353

$X$ is a string of length $N$ consisting of uppercase English letters.
$X$ is a palindrome.
$\le S$ in lexicographical order.
- That is, $X = S$ or $X$ is lexicographically smaller than $S$ .

Input is given from Standard Input in the following format:

 $T$  $\mathrm{case}_1$  $\mathrm{case}_2$  $\vdots$  $\mathrm{case}_T$

Here,

\mathrm{case}_i

represents the

i

-th test case.
Each test case is in the following format:

 $N$  $S$

T

lines. The

i

-th line should contain the answer for the

i

-th test case as an integer.