Practice on Toph

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

Wavio Palindrome

By Mohaimin66 · 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 x is the case number and y 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

Discussion

Statistics


81% Solution Ratio

NirjhorEarliest, Dec '19

likhon5Fastest, 0.2s

nfssdqLightest, 59 MB

omar24Shortest, 1119B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.