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=1e5+100;
int cnt[30],sum[maxn],need[30];
string s;
void init(int N){
    for(int i=0;i<=N+1;i++){
        sum[i]=0;
    }
    for(int i=0;i<=26;i++){
        cnt[i]=0;
    }
}

int getsum(int x,int k){

    return (k-x%k)%k;
}

int main() {
    ios::sync_with_stdio(false);
    int T;cin>>T;
    while(T--){
        int N,K;cin>>N>>K;
        cin>>s;
        s="#"+s;
        if(N%K!=0){
            cout<<-1<<endl;
            continue;
        }
        init(N);
        for(int i=1;i<=N;i++){
            cnt[s[i]-'a']+=1;
            sum[i]=sum[i-1]-getsum(cnt[s[i]-'a']-1,K)
                           +getsum(cnt[s[i]-'a'],K);
        }
        if(sum[N]==0){
            cout<<s.substr(1,N)<<endl;
            continue;
        }

        bool flag=false;
        for(int i=N;i>=1&&!flag;i--){
            cnt[s[i]-'a']-=1;
            if(sum[i-1]>N-i+1)
                continue;

            string t;
            for(int j=25;j>=0;j--){
                need[j]=getsum(cnt[j],K);
                for(int k=1;k<=need[j];k++){
                    t+=char('a'+j);
                }
            }
            while(t.size()<N-i+1) t='z'+t;
            if(t.compare(s.substr(i,N-i+1))<0)
                continue;

            t.clear();
            int f=-1;
            for(int k=s[i]-'a'+1;k<26;k++) {
                sum[i-1]-=getsum(cnt[k],K);
                cnt[k] += 1;
                need[k] = getsum(cnt[k], K);
                sum[i-1]+=getsum(cnt[k],K);
                if(sum[i-1]<=N-i+1){
                    f=k;break;
                }else{
                    sum[i-1]-=getsum(cnt[k],K);
                    cnt[k]-=1;
                    need[k]=getsum(cnt[k],K);
                }
            }

            if(f==-1)
                continue;
            for(int j=0;j<26;j++){
                for(int k=1;k<=need[j];k++)
                    t+=char('a'+j);
            }
            while(t.size()<N-(i+1)+1)
                t='a'+t;
            t=char('a'+f)+t;
            flag=true;
            cout<<s.substr(1,N-t.size())+t<<endl;
        }
        if(!flag)
            cout<<-1<<endl;
    }
    return 0;
}