Practice on Toph

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

Adorable String <3

By Humayra_037 · Limits 1s, 512 MB

There is a tie for 1st position in House Cup Tournament between house Gryffindor & Slytherin. The House Cup Tournament is a competition between the Houses of Hogwarts. The house which will win the cup, can contribute more to Code To Save A Mother event. Professor Severus Snape has given a task to Harry (Gryffindor House) & Malfoy (Slytherin House), who will solve the task first, his house will win the cup & the members of that house can contribute more in the event. The task is hard for Harry. So he asked your help to solve the task. Can you solve the task for Harry?

Let’s call a string adorable if its number of consonant(s) is 1 more then its number of vowel(s).

The letters “a, e, i, o, u” are vowels & others are consonant.

For more clarification, The string ‘abc’ is adorable because it has 2 consonants & 1 vowel and ‘b’ is also an adorable string as it has 1 consonant & 0 vowel.

You’re given a string. Your task is to count the number of adorable substring(s).

Input

Input starts with an integer TT (1T500)(1 ≤ T ≤ 500) , denoting the number of test cases.

The first line of each test case contains the length of string n,(1n5000000).n, (1≤n≤5000000).

It is guaranteed that the sum of nn does not exceed 50000005000000

The second line of each test case contains the string with only lower case letters.

Output

For each case, Output one integer denoting the number of adorable substring(s).

Sample

InputOutput
3
4
abcd
8
abcdefgh
10
aabcdeefgh
4
11
17

    Discussion

    Statistics


    56% Solution Ratio

    NirjhorEarliest, 1w ago

    SyedShajibFastest, 0.0s

    fsshakkhorLightest, 45 MB

    steinumShortest, 505B

    Submit

    Login to submit

    Related Contests