← 返回题目列表

Codeforces · 1980/A

A. 问题生成器

中文机器翻译题面 查看原题

Vlad 计划下个月举办 $$$m$$$ 轮。每轮应包含一个难度级别为“A”、“B”、“C”、“D”、“E”、“F”和“G”的问题。

Vlad 已经有一系列 $$$n$$$ 问题,其中第 $$$i$$$ 问题的难度级别为 $$$a_i$$$。这些问题可能还不够,所以他可能还要再想出几个问题。

Vlad 希望提出尽可能少的问题,因此他要求您找出他需要提出的最少问题数,以便举行 $$$m$$$ 轮。

例如,如果$$$m=1$$$,$$$n = 10$$$,$$$a=$$$ 'BGECDCBDED',那么他需要提出两道题:一道难度为'A',一道难度为'F'。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 50$$$, $$$1 \le m \le 5$$$)——分别是银行中的问题数量和即将到来的轮数。

每个测试用例的第二行包含一个字符串 $$$a$$$,从 'A' 到 'G' 包含 $$$n$$$ 个字符 - 银行问题的难度。

输出

对于每个测试用例,输出一个整数 - 需要解决 $$$m$$$ 轮的最少问题数。

示例

输入 #1

3
10 1
BGECDCBDED
10 2
BGECDCBDED
9 1
BBCDEFFGG

输出 #1

2
5
1