描述

你正在经营一个$DVD$图书馆。假设你有$k$个$DVD$驱动器，用户可以通过这些驱动器访问所请求的$DVD$内容。一个$DVD$驱动器在同一时间只能访问一张$DVD$的内容。当收到一个$DVD$请求时，如果该$DVD$已经在某个驱动器中，则无需任何操作。否则，你需要将请求的$DVD$插入一个空的驱动器。如果所有$k$个驱动器都已占用，则必须先从某个驱动器中移除一张$DVD$，再将请求的$DVD$插入该驱动器。目标是为整个请求序列提供服务时，最小化所需的$DVD$插入次数。

为了使问题更有趣，我们假设你已提前获知整个请求序列$x_1, x_2, \ldots, x_n$。此外，你必须按照顺序处理请求，即在处理$x_{i+1}$之前必须先处理$x_i$，其中$i = 1, 2, \ldots, n - 1$。你需要仔细规划如何处理每个请求，以使总$DVD$插入次数最小。显然，难点在于当收到一个未被任何驱动器缓存的$DVD$请求且所有驱动器都已占用时，如何确定应该移除哪张$DVD$。

例如，设$k = 2$，请求序列为$1, 2, 3, 1, 3, 1, 3$。对于前两个请求，只需将$DVD$ $1$和$2$分别插入两个驱动器。当第三个请求（即$DVD 3$）到达时，你必须从驱动器中移除$DVD 1$或$DVD 2$，以便将$DVD 3$插入其中一个驱动器。

• 如果选择第一种方案（即移除$DVD 1$），则剩余的请求（即请求$4-7$）至少需要再进行一次$DVD$插入。
• 如果选择第二种方案（即移除$DVD 2$），则剩余的请求（即请求$4-7$）无需再进行任何$DVD$插入。

不难验证，第二种方案是处理上述请求序列的最优方式，仅需三次$DVD$插入。

输入

第一行包含测试用例的数量$m$。每个测试用例的第一行包含两个数字$k$和$n$，其中$1 \leq k \leq 10$是$DVD$驱动器的数量，$1 \leq n \leq 100$是请求的数量。接下来的$n$行中，第$i$行包含第$i$个请求$x_i$。

输出

对于每个测试用例，你的程序需要在一行中输出处理整个请求序列所需的最小$DVD$插入次数。

输入数据 $1$

2
2 7
1
2
3
1
3
1
3
3 9
1
2
3
4
1
2
1
2
4

输出数据 $1$

3
4

来源

台湾 2004