BHADRADAWOW - Bhadra Da and Counting "wow"

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

Added by:BISHAL GAUTAM
Date:2015-12-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:my own

hide comments
2015-12-14 14:55:16
@gomathiganesan ignore the cases of the characters .....woW WOw WOW WoW wOw wow , all can be treated as same..
2015-12-12 21:00:36 gomathi ganesan
I'm getting TLE using C++.
Applied brute force technique.
Can anyone give me a hint ?
2015-12-12 19:11:26 Piyush Kumar
Please send this to tutorial.

=(Francky)=> Moved ; thanks.

Last edit: 2015-12-12 19:19:24
2015-12-12 09:58:23 abdou_93
Tutorial
2015-12-12 08:27:44 BISHAL GAUTAM
Now, Internal Error has been resolved.All submission has been rejudged.
2015-12-11 19:51:52 Vipul Srivastava
Internal Error
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.