I think all of us are familiar with word ‘wow’? Simply, when you find an easy problem (like this) in contest firstly you say “wow”, then starts coding.

Nowadays, Our famous “Bhadra Dada” is busy with codechef long challenge contest. So, he does not have time to set problems for a practice contest of his Jahangirnagar university. But he said that he wants to see ranklist to see the progress of students. Since, he is not setter of any problem of practice contest, he don’t have permission to see ranklist. So, I make a plan of giving him a encoded string, he can decode it by finding numbers of “wow” that can be made by picking up different characters from encoded string, which is equal to the number of solves of particular student. (Note: while picking up letters you can change the case of letters)

As I had already said, he is busy with codechef long challenge contest, your task is to help him by finding the answer of this task.

Input

First line begins with N giving number of student participating in contest. For student first line begins with L, giving the length of encoded string then next line containing encoded string.

Constraints

1 <= N <= 100

1 <= L <= 100

String will contain only upper and lowercase letters.

Output

For each student of input, print one line of output denoting the decoded number of solves by that student.

Example

Input:
2
6
wWoowW
3
wwW

Output:
2
0