{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME23/mandarin/PALPROB.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME23/russian/PALPROB.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003eLet us define the palindromeness of a string in the following way:\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eIf the string is not a palindrome, its\u0027 palindromeness is zero.\u003c/li\u003e\r\n\u003cli\u003eThe palindromeness of an one-letter string is \u003cb\u003e1\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003eThe palindromness of a string \u003cb\u003eS\u003c/b\u003e of the length greater than one is \u003cb\u003e1\u003c/b\u003e + \"palindromeness of the string that is formed by the first [|\u003cb\u003eS\u003c/b\u003e|/2] symbols of \u003cb\u003eS\u003c/b\u003e\".\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003eLet us consider some examples for better understanding:\u003c/p\u003e\r\n\u003cp\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eThe palindromeness of the string \u003cb\u003ezxqfd\u003c/b\u003e is \u003cb\u003e0\u003c/b\u003e, since the string is not a palindrome.\u003c/li\u003e\r\n\u003cli\u003eThe palindromeness of the string \u003cb\u003ea\u003c/b\u003e is \u003cb\u003e1\u003c/b\u003e, by definition.\u003c/li\u003e\r\n\u003cli\u003eThe palindromeness of the string \u003cb\u003eaa\u003c/b\u003e is \u003cb\u003e2\u003c/b\u003e, beucase for \"aa\" we get \u003cb\u003e1\u003c/b\u003e + palindromeness of \"a\", that is one, so we get \u003cb\u003e2\u003c/b\u003e.\u003c/li\u003e\r\n\u003cli\u003eThe palindromeness of the string \u003cb\u003eabacaba\u003c/b\u003e is \u003cb\u003e3\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003eYou are given a string \u003cb\u003eS\u003c/b\u003e. Find the sum of the palindromenesses of all the non empty substrings of \u003cb\u003e S\u003c/b\u003e (i.e. \u003cb\u003eS[i..j]\u003c/b\u003e, where \u003cb\u003ei\u003c/b\u003e \u003c\u003d \u003cb\u003ej\u003c/b\u003e). In other words, you have to calculate the sum of palindromenesses of \u003cb\u003eN * (N + 1) / 2\u003c/b\u003e substrings of \u003cb\u003eS\u003c/b\u003e, where \u003cb\u003eN\u003c/b\u003e is the length of \u003cb\u003eS\u003c/b\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe first and only line of every test case contains a single string \u003cb\u003eS\u003c/b\u003e for the corresponding test case.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each test case, output a single line containing an integer corresponding to the answer to the problem.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e3\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003eS\u003c/b\u003e consists only of lower-case Latin letters.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\u003cp\u003eSubtask 1 (15 points):\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003e|S|\u003c/b\u003e ≤ \u003cb\u003e100\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003eSubtask 2 (23 points):\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003e|S|\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003eSubtask 3 (62 points):\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003e|S|\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e"}},{"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\u003e2\r\nzxqfd\r\naba\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\u003cb\u003eExample case 1:\u003c/b\u003e There is no palindrome that occurs as the substring of \u003cb\u003ezxqfd\u003c/b\u003e and has the length more than \u003cb\u003e1\u003c/b\u003e. The individual characters are palindromes of the palindromeness of \u003cb\u003e1\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003e\u003cb\u003eExample case 2:\u003c/b\u003e The palindromeness of \u003cb\u003eaba\u003c/b\u003e is \u003cb\u003e2\u003c/b\u003e and the sum of the palindromenesses of single characters is \u003cb\u003e3\u003c/b\u003e.\u003c/p\u003e"}}]}