考え方
条件を満たす文字列$X$が，初めから何文字目で$S$と異なるかで場合分けして数え上げる．$S$と$i$文字目で異なる回文$X (\leq S)$としてあり得るものの個数は，次の積で求められる．
- $i-1$文字目までは$S$と一致するので1通り
- $i$文字目は，$S$より小さい必要があるので
ord(S[i - 1]) - ord('A')通り（$S$は0-indexedとしたので1ズレている） - $i+1$文字目から
x = (Sの文字数 + 1) // 2（$S$の真ん中までの文字数）までは自由に決めて良いので，$26^{x - i}$通り
さて，↑では1文字目からx = (Sの文字数 + 1) // 2（$S$の真ん中までの文字数）までが全て一致した文字列は考えていない．この文字列$X$を回文として具体的につくって，もし$X \leq S$を満たすなら，答えを+1する．
回答例 (Python)
mod = 998244353 T = int(input()) def f(N, S): ans = 0 for i in range(1, (N + 1) // 2 + 1): tmp = ord(S[i - 1]) - ord('A') tmp *= pow(26, (N + 1) // 2 - i, mod) tmp %= mod ans += tmp ans %= mod if N % 2: S2 = S[:N // 2] + S[N // 2] + S[:N // 2][::-1] else: S2 = S[:N // 2] + S[:N // 2][::-1] if S2 <= S: ans += 1 ans %= mod return ans for _ in range(T): N = int(input()) S = input() print(f(N, S))
