{"raw_statement":[{"iden":"problem statement","content":"Solve the following problem for $T$ test cases.\nGiven an integer $N$ and a string $S$, find the number of strings $X$ that satisfy all of the conditions below, modulo $998244353$.\n\n*   $X$ is a string of length $N$ consisting of uppercase English letters.\n*   $X$ is a palindrome.\n*   $X \\le S$ in lexicographical order.\n    *   That is, $X=S$ or $X$ is lexicographically smaller than $S$."},{"iden":"constraints","content":"*   $1 \\le T \\le 250000$\n*   $N$ is an integer between $1$ and $10^6$ (inclusive).\n*   In a single input, the sum of $N$ over the test cases is at most $10^6$.\n*   $S$ is a string of length $N$ consisting of uppercase English letters."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nHere, $\\mathrm{case}_i$ represents the $i$\\-th test case.\nEach test case is in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"5\n3\nAXA\n6\nABCZAZ\n30\nQWERTYUIOPASDFGHJKLZXCVBNMQWER\n28\nJVIISNEOXHSNEAAENSHXOENSIIVJ\n31\nKVOHEEMSOZZASHENDIGOJRTJVMVSDWW"},{"iden":"sample output 1","content":"24\n29\n212370247\n36523399\n231364016\n\nThis input contains five test cases.\nTest case #1:  \nThe $24$ strings satisfying the conditions are `AAA`$,$ `ABA`$,$ `ACA`$,...,$ `AXA`.\nTest case #2:  \n$S$ may not be a palindrome.\nTest case #3:  \nBe sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}