AT_abc242_e.[ABC242E] (∀x∀)

给定一个长度为 $N$ 的只包含大写字母的字符串 $S$，你需要计算出所有长度仍为 $N$ 的字符串 $X$ 的个数，要求其必须满足：

• $X$ 也只包含大写字母 $S$。
• $X$ 是一个回文字符串。
• $X$ 按字典序小于等于 $S$。

答案对 $998244353$ 取模。你需要回答 $T$ 组询问。

本题每个测试点包含多组测试数据。

输入数据按照以下形式给出：

$T$

$case_1$

$case_2$

$\vdots$

$case_T$

其中，$case_i$ 表示第 $i$ 组测试数据。

每组测试数据按以下形式给出：

$N$

$S$

输出共 $T$ 行，第 $i$ 行输出一个整数作为第 $i$ 组询问的答案。

数据规模与约定

• $1\le T\le 250000$
• $1\le N\le 10^6$
• 每个测试点的所有 $N$ 之和不超过 $10^6$。
• $S$ 是一个只包含大写字母的长度为 $N$ 的字符串。

样例解释 1

这个测试点包含 $5$ 组测试数据。

第 $1$ 组：满足条件的 $24$ 个字符串 $X$ 分别为：AAA,ABA,……,AXA。

第 $2$ 组：注意 $S$ 不一定是一个回文串。

第 $3$ 组：注意确保答案对 $998244353$ 取模。

Translate by @Ascnbeta.