Master Bates is a ravenous eater; due to his monstrous eating habits he is having some difficulties in performing. Dr. XXX has asked him to cut down on his intake. The doctor has prescribed the number of meals he can have in a day. Now Bates has got ‘k’ different varieties of foods (1 <= k <= 26) and he can have at most ‘m’ meals in a day (1 <= m <= 100) as prescribed by the doctor. Each variety of food is specified by a letter of the alphabet in lower case. A meal is defined as a string of contiguous characters of same type i.e. all the characters in the substring should be the same. Master Bates wants to eat as much as possible in his ‘m’ meals. Assuming each letter is 1 unit of food. What is the maximum amount he can consume?

Input

First line of input is the number of test cases (not more than 100). Each test case consists of 2 lines, first line of each case consists of an integer m (1 <= m <= 100).

Second line of each case consists of a string describing the food that he has for the day. There will be at most 100000 (10^5) characters in the string.

Output

Output one integer indicating the maximum amount of food he can consume.

Example

Input:
4
2
aaaabbaaaa
3
aabbbcccaaddddaaeeeee
5
abcde
1
aaaaabcde

Output:
8
12
5
5