# Practice on Toph

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

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.

## Input

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

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

It is guaranteed that the sum of $n$ does not exceed $5000000$

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


### Statistics

56% Solution Ratio

NirjhorEarliest, 1w ago

SyedShajibFastest, 0.0s

fsshakkhorLightest, 45 MB

steinumShortest, 505B