409413: GYM103535 A Fall with Fake Problem

A boy, whose ID is smzzl, loves solving problems on Codeforces. Some day, he was solving the following problem:

Given a string $$$S$$$, find the lexicographical-smallest string $$$T$$$, whose lexicographical order is no smaller than $$$S$$$, the times each letter appears in $$$T$$$ are multiples of $$$k$$$, and $$$|S|=|T|$$$.

"The problem is too easy! I want a harder one!"

So, he modified the problem. He no longer requires the times each letter appears in $$$T$$$ to be a multiple of $$$k$$$. Instead, he wants them to be a factor of $$$k$$$ or 0.

The problem actually becomes harder, but not so much harder. Fall, the teammate of smzzl, solved it immediately! And now, Fall wants you to solve it, so he can check his answer.

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 32$$$) – the number of test cases.

For each test case, there are two lines.

The first line contains two integers $$$n,k$$$($$$1 \leq n,k \leq 10^5$$$), which are the length of $$$S$$$ and the argument mentioned above.

The second line contains a string $$$S$$$, which only contains lower case letters.

It is guaranteed that the sum of $$$|S|$$$ over all test cases does not exceed $$$10^6$$$.

For each test case, output a string $$$T$$$ in a line, which is your answer. If there is no such $$$T$$$, output '-1' instead (without quotes).

2
5 6
aaaaa
10 18
abcabcabcd

aaabb
abcabcabcd