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](https://www.luogu.com.cn/user/767561).