12
12 3
zazasqzqsasq
1 1
z
1 1
a
15 4
abccbaabccbazaa
16 8
cadjfdsljfdkljds
6 2
baazaa
6 3
bosszb
6 1
qwerty
7 7
daaaaaa
14 2
acabcbdeffewzd
18 6
zzzzzzzzzzzzyyyyyz
9 4
aabaabbbc

zazasqzqsasq
z
a
-1
cbbbbbbbbccccccc
baazbz
bpbbpp
qwerty
ddddddd
acabcbdeffexdx
zzzzzzzzzzzzzzzzzz
-1

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
char a[maxn];
int n,k,b[30],c[30],las[maxn][27],top,d[30];
char ans[maxn];
bool isok(int nxt,int c[])
{
    while( nxt<=n )
    {
        for(int i='z';i>='a';i--)
        {
            if( c[i-'a']==0 )	continue;
            if( i>a[nxt] )	return true;
            else if( i<a[nxt] )	return false;
            else if( c[i-'a']>=las[nxt][i-'a'] ) {	c[i-'a'] -= las[nxt][i-'a'], nxt += las[nxt][i-'a']; break; }
            else if( c[i-'a']<las[nxt][i-'a'] )	return false;
        }
    }
    return true;
}
int main()
{
    int t; cin >> t;
    while( t-- )
    {
        cin >> n >> k >> ( a+1 );
        if( n%k!=0 )	{	cout << -1 << endl;	continue;}
        for(int i=n;i>=1;i--)
            for(int j='a';j<='z';j++)
            {
                if( a[i]==j )	las[i][j-'a'] = las[i+1][j-'a']+1;
                else	las[i][j-'a'] = 0;
            }

        int flag = 1,sum = n;
        for(int i=1;i<=n;i++)
        {
            if( flag )
            {
                for(char j=a[i];j<='z';j++)
                {
                    if( b[j-'a'] )
                    {
                        memcpy( c,b,sizeof c );
                        c[j-'a']--; c['z'-'a'] += sum;
                        if( j>a[i] || isok(i+1,c) )
                        {
                            ans[i] = j; b[j-'a']--;
                            if( j>a[i] )	flag = 0;
                            break;
                        }
                    }
                    else
                    {
                        if( sum<k )	continue;
                        memcpy( c,b,sizeof c );
                        c[j-'a'] += k-1; c['z'-'a'] += sum-k;
                        if( j>a[i] || isok(i+1,c) )
                        {
                            ans[i] = j; sum -= k; b[j-'a'] = k-1;
                            if( j>a[i] )	flag = 0;
                            break;
                        }
                    }
                }
            }
            else
            {
                b[0] += sum; int id = i;
                memset( d,0,sizeof d );
                for(char j='a';j<='z';j++)	while( b[j-'a'] )	ans[id++]=j, b[j-'a']--;
                break;
            }
        }
        for(int i=1;i<=n;i++)	cout << ans[i];
        cout << endl;
        for(int i=1;i<=n;i++)	memset( las[i],0,sizeof las[i] );
        memset( b,0,sizeof b );
    }
}

     				  	   							 	 						