#include <iostream>
#include <bits/stdtr1c++.h>
using namespace std;

int main()
{
    set<char> se;
    se.insert('a');
    se.insert('b');
    se.insert('d');
    se.insert('e');
    se.insert('o');
    se.insert('p');
    se.insert('q');
    int t,n,i,j;
    string s;
    cin>>t;
    while(t--){
        cin>>n>>n;
        cin>>s;
        if(n==0){
            for(i=s.size()-1;i>=0;i--){
                if(s[i]!='z'){
                    s[i]++;
                    while(se.count(s[i]))
                        s[i]++;
                    if(s[i]=='g') s[i]++;
                    cout<<s<<endl;
                    break;
                }else
                    s[i]='c';
            }
            if(i==-1)
                cout<<i<<endl;
            continue;
        }
        if(se.count(s[s.size()-1])){
            switch(s[s.size()-1]){
            case 'a':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'b'<<endl;
                break;
            case 'b':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'d'<<endl;
                break;
            case 'd':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'e'<<endl;
                break;
            case 'e':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'o'<<endl;
                break;
            case 'o':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'p'<<endl;
                break;
            case 'p':
                for(i=0;i<s.size()-1;i++)
                    cout<<s[i];
                cout<<'q'<<endl;
                break;
            case 'q':
                i=s.size()-1;
                while(i>=0&&s[i]=='q')
                    i--;
                j=i;
                while(j>=0&&s[j]=='z')
                    j--;
                if(j==-1)
                    cout<<j<<endl;
                else{
                    for(int k=0;k<j;k++)
                        cout<<s[k];
                    if(i-j>=1||se.count(s[j]+1)||!se.count(s[j])){
                        if(s[j]+1!='g')
                            cout<<char(s[j]+1);
                        else
                            cout<<'h';
                        if(se.count(s[j]+1)&&!se.count(s[j]))
                            i++;
                        if(!se.count(s[j]+1)&&se.count(s[j]))
                            i--;
                        for(j++,i++;i<s.size();j++,i++)
                            cout<<'a';
                        for(j=j;j<s.size();j++)
                            cout<<'c';
                        cout<<endl;
                    }else{
                        s[j]++;
                        while(!se.count(s[j]))
                            s[j]++;
                        if(s[j]=='g') s[j]++;
                        cout<<s[j];
                        for(j++;j<s.size();j++)
                            cout<<'a';
                        cout<<endl;
                    }
                }
                break;
            }
        }else{
            i=s.size()-1;
            while(s[i]=='z')
                i--;
            for(j=0;j<i;j++)
                cout<<s[j];
            if(se.count(s[i])){
                if(s[i]+1!='g')
                    cout<<char(s[i]+1);
                else
                    cout<<'h';
                if(se.count(s[i]+1)){
                    for(i++;i<s.size();i++)
                        cout<<'c';
                    cout<<endl;
                }else{
                    cout<<'a';
                    for(i+=2;i<s.size();i++)
                        cout<<'c';
                    cout<<endl;
                }
            }else{
                s[i]++;
                while(se.count(s[i]))
                    s[i]++;
                if(s[i]=='g') s[i]++;
                cout<<s[i];
                for(i++;i<s.size();i++)
                    cout<<'c';
                cout<<endl;
            }
        }
    }
    return 0;
}