You are given a string \(S\) of length \(N\) containing lowercase English letters and an integer \(K\). You can rearrange the characters of the string in any order. After that you split the string into several parts. Find the minimum number of parts in which you can split \(S\) such that each part satisfy the condition below:

• The frequency of every unique character in the part is at most \(K\).

Input Format

• The first line contains an integer \(T\), which denotes the number of test cases. For every test case:
• The first line contains two space-separated integers \(N\) and \(K\).
• The second line contains the string \(S\).

Output Format

For each test case, print the minimum number of parts in which you can split \(S\) such that each part satisfy the condition.

Constraints