{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Brother Qiu Shi likes to explore new things. Recently, he invented a new type of palindrome string called K-palindrome string! Today, he wants to test the kids with it.\n\nBrother Qiu Shi provided information related to a $K$-palindrome string:\n\u003e#####Any string belongs to a 0-palindrome string, including an empty string.\n\u003e#####A string of length $N$ called $S$ is a $K(k \\geq 1)$-palindrome string if and only if $S$ is a palindrome and its prefix of length $\\lfloor \\frac{N}{2} \\rfloor$ and suffix of length $\\lfloor \\frac{N}{2} \\rfloor$ are both $K-1$-palindrome strings.\n\u003e#####If a string is a $K$-palindrome string, it is said to have a palindrome value of $K$. A string can have multiple palindrome values, such as $S\u003dabaaba$, whose palindrome values can be 0, 1, 2, 3.\n\u003e#####The maximum palindrome value of a string is the maximum value among all its palindrome values.\n\u003e#####If a string $S$ has a maximum palindrome value of $ \\geq 1$, then $S$ must be a palindrome.\n\u003e#####A string $S$ is a palindrome if it reads the same forwards and backwards, such as aabaa, aba, a. But abc, abab, aacba are not palindromes.\n\u003e#####For a string $S$ of length $N$, it has $N+1$ prefixes and $N+1$ suffixes (not necessarily non-empty). For example, in abcde, there are 6 prefixes: an empty string, a, ab, abc, abcd, abcde; and 6 suffixes: an empty string, e, de, cde, bcde, abcde.\n\n####Brother Qiu Shi gives you a string $S$ and wants to ask you, what is the sum of the maximum palindrome values of all prefixes?"}},{"title":"Input","value":{"format":"MD","content":"The first line contains a string $S(0\u003c|S| \\leq 2\\cdot 10^6)$, which consists of uppercase letters (A-Z), lowercase letters (a-z), and numbers (0-9)."}},{"title":"Output","value":{"format":"MD","content":"Output an integer, representing the sum of the maximum palindrome values of all prefixes."}},{"title":"Sample 1","value":{"format":"MD","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\u003ez\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Sample 2","value":{"format":"MD","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\u003ea2Az\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Sample 3","value":{"format":"MD","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\u003eabacaba\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Sample 4","value":{"format":"MD","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\u003eCCeCeCCCee\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Sample 5","value":{"format":"MD","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\u003eZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e231\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Note","value":{"format":"MD","content":"#####Explanation for Sample 3:\n\n\u003e#####abacaba has 8 prefixes: an empty string, a, ab, aba, abac, abaca, abacab, abacaba;\n\n\u003e#####Let P(i) denote the maximum palindrome value of the i-th prefix, with an empty string being the 0-th prefix;\n\n\u003e#####Then P(0)\u003d0, P(1)\u003d1, P(2)\u003d0, P(3)\u003d2, P(4)\u003d0, P(5)\u003d0, P(6)\u003d0, P(7)\u003d3; so, $\\sum_{i\u003d0}^7 P(i)\u003d6$."}}]}