The value of a string is the sum of squared character frequencies. Remove exactly K characters to minimize its value.

Input

The first line contains T. Each test case contains K and then an uppercase string S.

• 1 <= T <= 100
• 0 <= K <= |S| <= 10^6

Output

For each test case, print the minimum possible value.

Example

Input

2
2
AAAB
3
ABCC

Output

2
1