{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eBaby volcano is helping his CCPC coach preparing a new CCPC training contest. He wants to generate high quality data on border tree(There is no need to know what border tree is), but he encounters some troubles. Could you please help him? \u003cbr\u003e\u003cbr\u003eIn this paragraph we formally define the data quality problem. For some string $s \u003d s_1s_2s_3\\cdots s_n$, we use $s[l:r]$ to denote the substring starts from $l$ and ends at $r$, if $l\u0026gt;r$, $s[l:r]$ is empty. We further define:\u003cbr\u003e$$Lborder_i \u003d \\max\\{0\\leq j \u0026lt; i\\ |\\ s[1:j] \u003d s[i-j+1:i]\\}$$\\\\to denote the longest border at some position $i$, then we define $D(i)$ to denote the length of border chain at position $i$: \\\\$$D(i) \u003d \\begin{cases} 0 \u0026amp; i\u003d0 \\\\ D(LBorder_i) + 1 \u0026amp; i \u0026gt; 0 \\end{cases}$$\\\\The quality $W$ of this string is define as the maximum of $D$:\\\\$$W \u003d \\max_{i \u003d 0}^{n} D(i)$$\u003cbr\u003e\u003cbr\u003eTo distinguish border tree with naive brute force algorithms, baby volcano need to generate strings such that its quality $W$ is as large as possible. \u003cbr\u003e\u003cbr\u003eNow given a string $s$, you could permute $s$ arbitrarily. What is the maximum quality $W$ you could reach after permuting $s$?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"In the first line there is a number $T$($T\\leq 20$), denotes the number of test cases.\u003cbr\u003eIn the next $T$ lines, for each line there is a string $s$($1\\leq |s|\\leq 10^5$), denotes the input string, all inputs are formed in lowercases."}},{"title":"Output","value":{"format":"HTML","content":"Output $T$ lines, for each line, you need to output \u0027\u0027Case #t: m\u0027\u0027(without quotes), where t is the index of this test case, m is the maximum quality you could reach after permuting."}},{"title":"Sample","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\u003e5\r\nabcde\r\nsankaranarayanan\r\nabbccaabc\r\nprogramming\r\nmonotone\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\nCase #2: 7\r\nCase #3: 3\r\nCase #4: 2\r\nCase #5: 3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}