CF1348C.Phoenix and Distribution

Phoenix has a string $s$ consisting of lowercase Latin letters. He wants to distribute all the letters of his string into $k$ non-empty strings $a_1, a_2, \dots, a_k$ such that every letter of $s$ goes to exactly one of the strings $a_i$. The strings $a_i$ do not need to be substrings of $s$. Phoenix can distribute letters of $s$ and rearrange the letters within each string $a_i$ however he wants.

For example, if $s = $ baba and $k=2$, Phoenix may distribute the letters of his string in many ways, such as:

• ba and ba
• a and abb
• ab and ab
• aa and bb

But these ways are invalid:

• baa and ba
• b and ba
• baba and empty string ($a_i$ should be non-empty)

Phoenix wants to distribute the letters of his string $s$ into $k$ strings $a_1, a_2, \dots, a_k$ to minimize the lexicographically maximum string among them, i. e. minimize $max(a_1, a_2, \dots, a_k)$. Help him find the optimal distribution and print the minimal possible value of $max(a_1, a_2, \dots, a_k)$.

String $x$ is lexicographically less than string $y$ if either $x$ is a prefix of $y$ and $x \ne y$, or there exists an index $i$ ($1 \le i \le min(|x|, |y|))$ such that $x_i$ < $y_i$ and for every $j$ $(1 \le j \lt i)$ $x_j = y_j$. Here $|x|$ denotes the length of the string $x$.

凤凰有一个由小写拉丁字母组成的字符串 $s$。他希望将字符串 $s$ 中的所有字母分配到 $k$ 个非空字符串 $a_1, a_2, \dots, a_k$ 中，使得 $s$ 的每个字母恰好被分配到某个 $a_i$ 中。这些字符串 $a_i$ 不必是 $s$ 的子串。凤凰可以以任意方式分配 $s$ 的字母，并可在每个字符串 $a_i$ 内任意重排其字母。

例如，若 $s = $ baba 且 $k=2$，凤凰可将字符串的字母以多种方式分配，例如：

• ba 和 ba
• a 和 abb
• ab 和 ab
• aa 和 bb

但以下方式是无效的：

• baa 和 ba
• b 和 ba
• baba 和空字符串（因所有 $a_i$ 必须非空）

凤凰希望将字符串 $s$ 的字母分配到 $k$ 个字符串 $a_1, a_2, \dots, a_k$ 中，使得其中字典序最大的字符串尽可能小，即最小化 $\max(a_1, a_2, \dots, a_k)$。请帮助他找到最优分配方案，并输出 $\max(a_1, a_2, \dots, a_k)$ 的最小可能值。

字符串 $x$ 字典序小于字符串 $y$，当且仅当满足以下任一条件：

• $x$ 是 $y$ 的真前缀（即 $x$ 是 $y$ 的前缀且 $x \ne y$），或
• 存在下标 $i$（$1 \le i \le \min(|x|, |y|)$），使得 $x_i < y_i$，且对所有 $j$（$1 \le j < i$）均有 $x_j = y_j$。
  此处 $|x|$ 表示字符串 $x$ 的长度。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Each test case consists of two lines.

The first line of each test case consists of two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of string $s$ and the number of non-empty strings, into which Phoenix wants to distribute letters of $s$, respectively.

The second line of each test case contains a string $s$ of length $n$ consisting only of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases is $\le 10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。每个测试用例由两行组成。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$），分别表示字符串 $s$ 的长度，以及 Phoenix 希望将 $s$ 中的字母分配到的非空字符串的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，该字符串仅由小写拉丁字母组成。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

Print $t$ answers — one per test case. The $i$-th answer should be the minimal possible value of $max(a_1, a_2, \dots, a_k)$ in the $i$-th test case.

输出 $t$ 个答案——每个测试用例一个答案。第 $i$ 个答案应为第 $i$ 个测试用例中 $max(a_1, a_2, \dots, a_k)$ 的最小可能值。

In the first test case, one optimal solution is to distribute baba into ab and ab.

In the second test case, one optimal solution is to distribute baacb into abbc and a.

In the third test case, one optimal solution is to distribute baacb into ac, ab, and b.

In the fourth test case, one optimal solution is to distribute aaaaa into aa, aa, and a.

In the fifth test case, one optimal solution is to distribute aaxxzz into az, az, x, and x.

In the sixth test case, one optimal solution is to distribute phoenix into ehinopx.

在第一个测试用例中，一种最优解是将字符串 baba 拆分为 ab 和 ab。

在第二个测试用例中，一种最优解是将字符串 baacb 拆分为 abbc 和 a。

在第三个测试用例中，一种最优解是将字符串 baacb 拆分为 ac、ab 和 b。

在第四个测试用例中，一种最优解是将字符串 aaaaa 拆分为 aa、aa 和 a。

在第五个测试用例中，一种最优解是将字符串 aaxxzz 拆分为 az、az、x 和 x。

在第六个测试用例中，一种最优解是将字符串 phoenix 拆分为 ehinopx。