{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlex is a private jewel collector.\u003c/p\u003e\u003cp\u003eRecently, he purchased a piece of jewelry, a bunch of $$$n$$$ gemstones. The gemstones have $$$26$$$ different types, labeled from \u003cspan class\u003d\"tex-font-style-tt\"\u003ea\u003c/span\u003e to \u003cspan class\u003d\"tex-font-style-tt\"\u003ez\u003c/span\u003e. He wants to split the jewelry and combine them into a jewel matrix.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/b5a597a89aa5cabb0884db5010a26cda?v\u003d1719940206\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eAlex will choose $$$d \\in \\{1,2,\\cdots, n\\}$$$, the width of the jewel matrix. Then, he will split the jewelry and get $$$\\left\\lfloor \\frac{n}{d} \\right\\rfloor$$$ bunches of gemstones with length $$$d$$$ and a bunch of length $$$n \\bmod d$$$ if $$$d$$$ doesn\u0027t divide $$$n$$$. All $$$\\left\\lfloor \\frac{n}{d} \\right\\rfloor$$$ bunches with length $$$d$$$ will be permuted as rows of the jewel matrix.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d5842df573b2d1e1e3bbde2d47b1023c?v\u003d1719940206\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eAlex wonders how many different jewel matrix he can get. Two jewel matrix are considered different if and only if they have different width, or it is at least one row different.\u003c/p\u003e\u003cp\u003eAs the results can be very large, output it modulo $$$998244353$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input gives the number of test cases, $$$T\\ (1\\le T \\le 1000)$$$. $$$T$$$ test cases follow.\u003c/p\u003e\u003cp\u003eFor each test case, the only line contains a string $$$s_1s_2\\cdots s_n\\ (1\\le n \\le 3 \\times 10^5, s_i \\in \\{\\texttt{a,b,c},\\cdots,\\texttt{z}\\})$$$, representing the jewelry.\u003c/p\u003e\u003cp\u003eThe sum of $$$n$$$ in all test cases doesn\u0027t exceed $$$10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output one line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e\", where $$$\\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\\texttt{y}$$$ is the answer modulo $$$998244353$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\nababccd\naab\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 661\nCase #2: 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}