题目描述

在大陆战争结束后的和平年代，邮政公司的自动手记人偶 violet 接到了一项特殊任务。一位名叫奥斯卡·韦伯的著名作家留下了一箱未完成的信件和手稿，这些文件被混乱地堆放在一起，形成了一个长长的序列。

根据韦伯先生的遗愿，这些文件需要被整理成 k 个连续的信件集，分别发送给不同的收件人。每个信件集代表原序列中一个或多个连续的文件片段组成的子序列。violet 需要将这些信件集进行分割，使得所有信件集的“最小情感指数”（Minimum Emotional Index，简称 MEI）的值最大。

情感指数（EI）表示一个信件集中缺失的最小情感类型，情感类型用非负整数表示。例如，如果一个信件集中包含情感类型 1 和 2，但缺失 0，则其 EI 为 0；如果包含 0 和 2，但缺失 1，则 EI 为 1；如果 0、1、2 都包含，则检查是否包含 3，以此类推。

你需要帮助 violet 确定最佳的分割方案，使得所有信件集的 EI 的最小值尽可能大。

输入格式

第一行包含一个整数 t——测试用例的数量。

每个测试用例的第一行包含两个整数 n 和 k——文件序列的长度和需要分割成的信件集数量。

每个测试用例的第二行包含 n 个整数 a[i]——表示每个文件片段所包含的情感类型。

输出格式

对于每个查询，输出一个整数——最大的 x 值，使得存在一种将文件序列分割成 k 个信件集的方式，其中所有信件集的情感指数的最小值等于 x。

输入输出样例

输入样例 #1

7
1 1
0
5 1
0 1 3 2 4
6 2
2 1 0 0 1 2
5 5
0 0 0 0 0
5 2
2 3 4 5 6
6 2
0 0 1 1 2 2
4 4
1 0 0 0

输出样例 #1

1
5
3
1
0
1
0

样例说明 #1

在第一个样例中，只有一个文件片段包含情感类型 0。由于只能形成一个信件集，其 EI 为 1（缺失的最小情感类型是 1），所以输出为 1。

在第二个样例中，整个序列包含情感类型 0、1、2、3、4，但缺失 5。因此，EI 为 5，输出为 5。

在第三个样例中，我们可以将序列分割为 [2, 1, 0] 和 [0, 1, 2]。第一个信件集的 EI 为 3（缺失 3），第二个信件集的 EI 也为 3，所以最小值为 3，输出为 3。

说明/提示

数据范围

对于 10% 的数据，1 ≤ t ≤ 100，1 ≤ k ≤ n ≤ 100，0 ≤ a[i] ≤ 100，所有测试用例的 n 之和不超过 1000。

对于 100% 的数据，1 ≤ t ≤ 10^4，1 ≤ k ≤ n ≤ 10^5，0 ≤ a[i] ≤ 10^9，所有测试用例的 n 之和不超过 2 * 10^5。