# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

**Palindrome** is a string which reads the same from both right to left and left to right. Formally, a string `$s_1s_2...s_n$`

of length `$n$`

is a palindrome if `$s_i = s_{n-i+1}$`

, for all `$i \leq \frac{n}{2}$`

.
Example: `$a$`

, `$aa$`

, `$aba$`

, `$cdadc$`

are palindromes. But `$ab$`

, `$abb$`

, `$cdbc$`

are not palindromes.

Now let's define **Wavio Palindrome**. Palindromic string of length `$n$`

is a Wavio Palindrome if its prefix of length ⌈`$\frac{n}{2}$`

⌉ is also a palindrome.
Example: `$aaa$`

, `$ababa$`

, `$abaaba$`

are Wavio Palindromes. But `$abba$`

, `$abbba$`

are not.

Given a string of length `$l$`

, 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 `$T$`

.

The first line of each test case contains an integer `$l$`

, length of the input string.

The next line of the test case is the input string `$S$`

of length `$l$`

. It will consist of only lowercase English alphabet.

`$1\leq T \leq10$`

.`$1\leq l \leq1000000$`

.

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.

Input | Output |
---|---|

3 4 aaaa 8 abaabaaa 4 abab | Case 1: 3 Case 2: 2 Case 3: 0 |