Fall with Fake Problem

Problem Description

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.

Input

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$.

Output

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).

Sample Input

2

5 6

aaaaa

10 18

abcabcabcd

Sample Output

aaabb

abcabcabcd

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）