Wavio Palindrome

Mohaimin66 The Tough Winter Spar, 20...
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.

Input

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.

  • 1T101\leq T \leq10
  • 1l10000001\leq l \leq1000000

Output

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.

Sample

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

Submit

Login to submit.

Contributors

Statistics

86% Solution Ratio
NirjhorEarliest, Dec '19
samiulsamiFastest, 0.0s
samiulsamiLightest, 136 kB
omar24Shortest, 1119B
Toph uses cookies. By continuing you agree to our Cookie Policy.