题目描述

给定正整数 $N$ 和长度为 $N$ 的字符串 $S$，你的任务是计算有多少个长度为 $N$ 的回文字符串 $X$，使得 $X \leq S$。计算结果对 $998244353$ 取模。$S$ 和 $T$ 均只包含大写英文字母。

输入格式

第一行输入一个整数 $T$ 代表多组数据的数量。

每组数据先输入一个整数 $N$ 然后输入一个字符串 $S$

输出格式

输出一共输出 $T$ 行，每行一个整数代表答案。

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

24
29
212370247
36523399
231364016

提示

总共有 $T$ 组数据。$T \leq 250000$, $N \leq 10^6$，所有 $S$ 的字母总数不超过 $10^6$。