{"problem":{"name":"(∀x∀)","description":{"content":"Solve the following problem for $T$ test cases. Given an integer $N$ and a string $S$, find the number of strings $X$ that satisfy all of the conditions below, modulo $998244353$. *   $X$ is a string","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc242_e"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc242_e","tags":[],"sample_group":[["5\n3\nAXA\n6\nABCZAZ\n30\nQWERTYUIOPASDFGHJKLZXCVBNMQWER\n28\nJVIISNEOXHSNEAAENSHXOENSIIVJ\n31\nKVOHEEMSOZZASHENDIGOJRTJVMVSDWW","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$."]],"created_at":"2026-03-03 11:01:14"}}