311390: CF1980A. Problem Generator

A. Problem Generatortime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vlad is planning to hold $m$ rounds next month. Each round should contain one problem of difficulty levels 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.

Vlad already has a bank of $n$ problems, where the $i$-th problem has a difficulty level of $a_i$. There may not be enough of these problems, so he may have to come up with a few more problems.

Vlad wants to come up with as few problems as possible, so he asks you to find the minimum number of problems he needs to come up with in order to hold $m$ rounds.

For example, if $m=1$, $n = 10$, $a=$ 'BGECDCBDED', then he needs to come up with two problems: one of difficulty level 'A' and one of difficulty level 'F'.

Input

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 50$, $1 \le m \le 5$) — the number of problems in the bank and the number of upcoming rounds, respectively.

The second line of each test case contains a string $a$ of $n$ characters from 'A' to 'G' — the difficulties of the problems in the bank.

Output

For each test case, output a single integer — the minimum number of problems that need to come up with to hold $m$ rounds.

ExampleInput

3
10 1
BGECDCBDED
10 2
BGECDCBDED
9 1
BBCDEFFGG

Output

2
5
1

**题目大意：**

Vlad下个月计划举行 $ m $ 轮比赛。每轮比赛应该包含一个难度级别为 'A', 'B', 'C', 'D', 'E', 'F', 和 'G' 的问题。

Vlad已经有 $ n $ 个问题的题库，其中第 $ i $ 个问题的难度级别为 $ a_i $。可能没有足够的问题，所以他可能需要想出更多的问题。

Vlad想要尽可能少地想出问题，所以他要求你找出他需要想出多少个问题才能举行 $ m $ 轮比赛。

**输入数据格式：**

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

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

每个测试用例的第二行包含一个由 $ n $ 个字符组成的字符串 $ a $，字符从 'A' 到 'G' —— 题库中问题的难度。

**输出数据格式：**

对于每个测试用例，输出一个整数 —— 为了举行 $ m $ 轮比赛需要想出的最少数量的新问题。

**示例：**

**输入：**
```
3
10 1
BGECDCBDED
10 2
BGECDCBDED
9 1
BBCDEFFGG
```

**输出：**
```
2
5
1
```

**题目翻译及解释：**

Vlad计划在下个月举行多轮比赛，每轮比赛都需要包含一个难度级别为A到G的问题。他已经有了一些问题，但是可能不足以支撑所有轮次的比赛，因此需要创造新问题。Vlad想要尽可能少地创造新问题，因此他请你帮助计算他至少需要创造多少个新问题，以便能够顺利进行所有轮次的比赛。

输入部分指定了测试用例的数量，每个测试用例包括题库中问题的数量和即将进行的轮数，以及题库中每个问题的难度级别。输出部分要求对于每个测试用例，输出Vlad至少需要创造的新问题数量。

在给出的例子中，对于第一组测试数据，Vlad需要创造两个新问题，一个难度为A的问题和一个难度为F的问题；对于第二组测试数据，由于需要两轮比赛，而题库中的问题不足以覆盖所有难度级别，因此Vlad需要创造五个新问题；对于第三组测试数据，Vlad只需要创造一个新问题，因为题库中已经有所有需要的难度级别的问题，除了A级别。**题目大意：** Vlad下个月计划举行 $ m $ 轮比赛。每轮比赛应该包含一个难度级别为 'A', 'B', 'C', 'D', 'E', 'F', 和 'G' 的问题。 Vlad已经有 $ n $ 个问题的题库，其中第 $ i $ 个问题的难度级别为 $ a_i $。可能没有足够的问题，所以他可能需要想出更多的问题。 Vlad想要尽可能少地想出问题，所以他要求你找出他需要想出多少个问题才能举行 $ m $ 轮比赛。 **输入数据格式：** 输入的第一行包含一个整数 $ t $ ($ 1 \le t \le 1000 $) —— 测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $ ($ 1 \le n \le 50 $, $ 1 \le m \le 5 $) —— 题库中问题的数量和即将进行的轮数。 每个测试用例的第二行包含一个由 $ n $ 个字符组成的字符串 $ a $，字符从 'A' 到 'G' —— 题库中问题的难度。 **输出数据格式：** 对于每个测试用例，输出一个整数 —— 为了举行 $ m $ 轮比赛需要想出的最少数量的新问题。 **示例：** **输入：** ``` 3 10 1 BGECDCBDED 10 2 BGECDCBDED 9 1 BBCDEFFGG ``` **输出：** ``` 2 5 1 ``` **题目翻译及解释：** Vlad计划在下个月举行多轮比赛，每轮比赛都需要包含一个难度级别为A到G的问题。他已经有了一些问题，但是可能不足以支撑所有轮次的比赛，因此需要创造新问题。Vlad想要尽可能少地创造新问题，因此他请你帮助计算他至少需要创造多少个新问题，以便能够顺利进行所有轮次的比赛。 输入部分指定了测试用例的数量，每个测试用例包括题库中问题的数量和即将进行的轮数，以及题库中每个问题的难度级别。输出部分要求对于每个测试用例，输出Vlad至少需要创造的新问题数量。 在给出的例子中，对于第一组测试数据，Vlad需要创造两个新问题，一个难度为A的问题和一个难度为F的问题；对于第二组测试数据，由于需要两轮比赛，而题库中的问题不足以覆盖所有难度级别，因此Vlad需要创造五个新问题；对于第三组测试数据，Vlad只需要创造一个新问题，因为题库中已经有所有需要的难度级别的问题，除了A级别。