Palindrome is a string which reads the same from both right to left and left to right. Formally, a string of length is a palindrome if , for all .
Example: , , , are palindromes. But , , are not palindromes.
Now let's define Wavio Palindrome. Palindromic string of length is a Wavio Palindrome if its prefix of length ⌈⌉ is also a palindrome.
Example: , , are Wavio Palindromes. But , are not.
Given a string of length , 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 .
The first line of each test case contains an integer , length of the input string.
The next line of the test case is the input string of length . It will consist of only lowercase English alphabet.
For each test case, print a line in the form "Case x: y" where x is the case number and y is the number of Wavio Palindromic substring in the input string.
3 4 aaaa 8 abaabaaa 4 abab
Case 1: 3 Case 2: 2 Case 3: 0