String rotation and vowels
Problem
You are given an even length string containing only loowercase alphabets. You need to count the number of rotations(strings with different combination of the letters) of the given string that contains more vowels in the first half than in the second half.
Input Format
-
First line T denoting the number of test cases For the next T lines
-
First line: An even integer N denoting the length of the string S
- Second line: S denoting the string of length N
Constraints
1<=T<=10 2<=N<=100000
Output Format
- For every test case, print answer in a new line.
Time Limit: 0.2
Memory Limit: 256
Source Limit:
Explanation
For test case 1:
All rotations of the strings are abcd, dabc, cdab,bcda.
Rotation 1 and 2 contains more vowels in the first half than second. So Answer is 2.
