Wavio Palindrome

Limits 1s, 512 MB

Palindrome is a string which reads the same from both right to left and left to right. Formally, a string s1s2...sns_1s_2...s_n of length nn is a palindrome if si=sni+1s_i = s_{n-i+1}, for all in2i \leq \frac{n}{2}.

Example: aa, aaaa, abaaba, cdadccdadc are palindromes. But abab, abbabb, cdbccdbc are not palindromes.

Now let's define Wavio Palindrome. Palindromic string of length nn is a Wavio Palindrome if its prefix of length ⌈n2\frac{n}{2}⌉ is also a palindrome.

Example: aaaaaa, ababaababa, abaabaabaaba are Wavio Palindromes. But abbaabba, abbbaabbba are not.

Given a string of length ll, you have to count the number of palindromic substring of the given string having length greater than 2 and which is also a Wavio Palindrome. If any Wavio Palindromic substring occurs more than once in the given string, all its occurrences should be counted.


The first line is the number of test cases TT. The first line of each test case contains an integer ll, length of the input string. The next line of the test case is the input string SS of length ll. It will consist of only lowercase English alphabet.


For each test case, print a line in the form "Case x: y" where xx is the case number and yy is the number of Wavio Palindromic substring in the input string.


Case 1: 3
Case 2: 2
Case 3: 0