{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eA palindrome is a string, a sequence of characters, that reads the same backward as forward, such as a, aba or baab.\u003c/p\u003e \n \u003cp\u003eA substring of one string is a contiguous sequence of characters within the string. For instance, a, aba and baab are substrings of abaab.\u003c/p\u003e \n \u003cp\u003eTwo strings are the same if and only if their lengths are the same, their first characters are the same, their second characters are the same, etc.\u003c/p\u003e \n \u003cp\u003eYou are given a string \u003cvar\u003eS\u003c/var\u003e of length \u003cvar\u003eN\u003c/var\u003e containing only lowercase letters and you are asked to calculate the number of distinct palindromes appeared in each substring of \u003cvar\u003eS\u003c/var\u003e.\u003c/p\u003e \n \u003cp\u003eFor the sake of clarity, let \u003cvar\u003eS[L..R]\u003c/var\u003e as the substring of \u003cvar\u003eS\u003c/var\u003e from the \u003cvar\u003eL\u003c/var\u003e-th character to the \u003cvar\u003eR\u003c/var\u003e-th character (\u003cvar\u003eL ≤ R\u003c/var\u003e), \u003cvar\u003ef(T)\u003c/var\u003e as the number of distinct palindromes that are substrings of \u003cvar\u003eT\u003c/var\u003e, and you need to determine the value of the following formula:\u003c/p\u003e \n \u003cp\u003e\u003cvar\u003e\u003cvar\u003e\u003cimg width\u003d\"300\" height\u003d\"66\" title\u003d\"formula.png\" style\u003d\"width:300px;height:66px;float:none;\" src\u003d\"CDN_BASE_URL/3af11d89351e65aae531d8957a5df6f2?v\u003d1659380860\" border\u003d\"0\" vspace\u003d\"0\" hspace\u003d\"0\"\u003e\u003cbr\u003e\u003c/var\u003e\u003c/var\u003e\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe first line contains one integer \u003cvar\u003eT\u003c/var\u003e , indicating the number of test cases.\u003c/p\u003e \n \u003cp\u003eThe following lines describe all the test cases.\u003c/p\u003e \n \u003cp\u003eEach of the following \u003cvar\u003eT\u003c/var\u003e lines describes one test case and contains only a string \u003cvar\u003eS\u003c/var\u003e consisting of lowercase letters. Let the length of \u003cvar\u003eS\u003c/var\u003e be \u003cvar\u003eN\u003c/var\u003e.\u003c/p\u003e \n \u003cp\u003e1 ≤ \u003cvar\u003eT\u003c/var\u003e ≤ 1000, 1 ≤ \u003cvar\u003eN\u003c/var\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e.\u003c/p\u003e \n \u003cp\u003eIt is guaranteed that the sum of \u003cvar\u003eN\u003c/var\u003e in all the test cases does not exceed 10\u003csup\u003e6\u003c/sup\u003e.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case, print \"Case #x: y\" (without quotes) in one line, indicating that this is the \u003cvar\u003ex\u003c/var\u003e-th test case and the answer for this test case is \u003cvar\u003ey\u003c/var\u003e.\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e3\r\nak\r\nace\r\nabaab\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003eCase #1: 6\r\nCase #2: 20\r\nCase #3: 105\u003c/pre\u003e \n "}}]}