{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003clink rel\u003d\"stylesheet\" href\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css\" integrity\u003d\"sha384-wITovz90syo1dJWVh32uuETPVEtGigN07tkttEqPv+uR2SE/mbQcG7ATL28aI9H0\" crossorigin\u003d\"anonymous\"\u003e\r\n\u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.js\" integrity\u003d\"sha384-/y1Nn9+QQAipbNQWU65krzJralCnuOasHncUFXGkdwntGeSvQicrYkiUBwsgUqc1\" crossorigin\u003d\"anonymous\"\u003e\u003c/script\u003e\r\n\u003cscript src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/contrib/auto-render.min.js\"\u003e\u003c/script\u003e\r\n\u003cscript\u003e// \u003c![CDATA[\r\ndocument.addEventListener(\"DOMContentLoaded\", function(){\r\n renderMathInElement(\r\n document.body,{\r\n delimiters: [\r\n {left: \"$$\", right: \"$$\", display: true},\r\n {left: \"$\", right: \"$\", display: false}]})});\r\n// ]]\u003e\u003c/script\u003e\r\n\r\n\u003cp\u003eA palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left.\u003c/p\u003e\r\n\u003cp\u003eChiaki has a string $s$ and she can perform the following operation at most once:\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003echoose two integer $i$ and $j$ ($1 \\le i, j \\le |s|$).\u003c/li\u003e\r\n\u003cli\u003eswap $s_i$ and $s_j$.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003eChiaki would like to know the longest palindromic substring of string after the operation.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThere are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\r\n\u003cp\u003eThe first line contains a non-empty string $s$ ($1 \\le |s| \\le 10^6$) consisting of lowercase and uppercase letters.\u003c/p\u003e\r\n\u003cp\u003eIt is guaranteed that the sum of all $|s|$ does not exceed $10^6$.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, output an integer denoting the answer.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e10\r\na\r\nxxxx\r\nssfs\r\naaabbacaa\r\nmissimxx\r\nababababgg\r\ndfsfsdgdg\r\nasdsasdswe\r\nchiaki\r\nteretwer\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n4\r\n3\r\n8\r\n6\r\n9\r\n6\r\n9\r\n3\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003c/div\u003e"}}]}