{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ consisting of lowercase letters. For each contiguous substring of $S$ (there are $|S|(|S|+1)/2$ such substrings), solve the following problem, and compute the sum of the answers.\nProblem: You are given a string $T$ consisting of lowercase letters. Compute the minimum possible length of a string that can be obtained from $T$ by repeatedly applying the following operation an arbitrary number of times.\n\n*   Take a prefix of $T$ that is a palindrome of odd length. Let the length be $2k+1$. Remove the first $k$ letters of $T$."},{"iden":"constraints","content":"*   $1\\leq |S|\\leq 10^6$\n*   $S$ consists of lowercase letters."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$S$"},{"iden":"sample input 1","content":"abab"},{"iden":"sample output 1","content":"16\n\nIf $T$ is `a` or `b`, the answer is $1$.\nIf $T$ is `ab` or `ba`, the answer is $2$.\nIf $T$ is `aba` or `bab`, applying the operation with $k=1$ once is optimal, and the answer is $2$.\nIf $T$ is `abab`, applying the operation with $k=1$ twice is optimal, and the answer is $2$.\nTherefore, the whole answer is $1\\times 4 + 2\\times 3 + 2\\times 2 + 2\\times 1 = 16$."},{"iden":"sample input 2","content":"abacaba"},{"iden":"sample output 2","content":"67"},{"iden":"sample input 3","content":"tabatadebatabata"},{"iden":"sample output 3","content":"739"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}