Dhinchak in Mandi

0

0 votes
Easy
Problem

Dhinchak Pooja was invited as judge for a singing competition in Exodia. However she has a strange way of judging. She checks number of times "mandi" can be formed by rearranging the lyrics (characters) and gives that score to that performer. Since this is a tough job, she asked you to write a program to give score to each performer.

Note that the "Mandi" you have to form is case insensitive


Input

First line contains T - number of performers.

For each test case,

First line contains - n - the number of characters in lyrics (song).

Second line contains a string of n characters. (lower case or upper case)


Output

For each test case, output an integer denoting the score of performer.


Constraints

  • 1 <= T <= 1000
  • 1 <= n <= 1000

Example

Input

2

28

DilonKaShooterHaiMeraScooter

15

mmmaaannndddiii

output

1

3


Explanation

For 1st testcase -

There is/are

1 'm'

3 'a'

1 'n'

1 'd'

1 'i'

So you can form 1 "mandi".

For 2nd testcase,

There is / are

3 'm'

3 'a'

3 'n'

3 'd'

3 'i'

So you can form 3 "mandi".

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?