Phoenix va phan phoi chu cai

Cho một xâu $s$ gồm $n$ chữ cái Latin thường. Bạn cần chia tất cả các chữ cái của $s$ vào $k$ xâu khác rỗng $a_1,a_2,\dots ,a_k$ sao cho mỗi chữ cái của $s$ thuộc đúng một xâu $a_i$. Các xâu $a_i$ không cần là xâu con của $s$: bạn được phép phân phối các chữ cái và sắp xếp lại thứ tự các chữ cái bên trong mỗi xâu $a_i$ tuỳ ý.

Trong tất cả các cách chia hợp lệ, hãy tìm cách làm cho xâu lớn nhất theo thứ tự từ điển trong số $a_1,a_2,\dots ,a_k$ là nhỏ nhất có thể. In ra giá trị nhỏ nhất đó của $max(a_1,a_2,\dots ,a_k)$.

Xâu $x$ nhỏ hơn xâu $y$ theo thứ tự từ điển nếu $x$ là tiền tố thực sự của $y$, hoặc tại vị trí đầu tiên mà chúng khác nhau, chữ cái của $x$ nhỏ hơn chữ cái của $y$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ gồm hai dòng:
  • Dòng thứ nhất chứa hai số nguyên $n$ và $k$.
  • Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các chữ cái Latin thường.

Dữ liệu ra

In $t$ dòng, mỗi dòng là đáp án của một bộ dữ liệu: giá trị nhỏ nhất có thể của $max(a_1,a_2,\dots ,a_k)$.

Ràng buộc

• $1\le t\le 1000$
• $1\le k\le n\le {10}^5$
• Tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Ví dụ