You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 1.5 s

Memory Limit: 256.0 MB

Description

You are given a string S of length N. A string is considered beautiful if all the characters of the same type appear together in consecutive groups, without being separated by any other characters.

For example, a beautiful string might consist of characters like:

• "aaa"
• "eeeiaaouuu"
• "uuuu"
• "aeiou"
• "eeeiiooouuaaaaa"

But string "aea", "eeaeiou", "ouuaaau" are not beautiful.

In each operation, you can select an index \(i\) (\(1 ≤ i ≤ N\)) and perform one of the following transformations on the character at that position:

• If the current character at index \(S_i\) is 'a", you can change it to 'e'.
• If the current character at index \(S_i\) is 'e', you can change it to 'i'.
• If the current character at index \(S_i\) is 'i', you can change it to 'o'.
• If the current character at index \(S_i\) is 'o', you can change it to 'u'.
• If the current character at index \(S_i\) is 'u', you can change it to 'a'.

You need to find the minimum number of operations required to transform the string S into a beautiful string.

Input

First line \(T\), the number of test cases.
In each test case, first line a positive integer N which represent length of the string S.
Second line, a string S.

\(1<=T<=10^4\)
\(1<=N<=10^5\)
String S={'a','e','i','o','u'}.
Sum of N overall test cases doesn't exceed \(10^5\).

Output

In each test case, print the minimum number of operations needed to make string S beautiful.

Sample

3

4

aaea

5

eaeau

6

eeaauu

1

1

0

First test case:
Initially, String S = "aaea".
We can select index 4 and change S[4]='a' to S[4]='e'.
Now string S looks like "aaee", which is a beautiful string.
So only one operation is required.

Second test case :
Initially, String S = "eaeau".
We can select index 2 and change S[2]='a' to S[2]='e'.
Now string S looks like "eeeau", which is a beautiful string.

Third test case: 
String S is already beautiful.