You are given a string s consisting of lowercase English letters and a number k. Let's call a string consisting of lowercase English letters beautiful if the number of occurrences of each letter in that string is divisible by k. You are asked to find the lexicographically smallest beautiful string of length n, which is lexicographically greater or equal to string s. If such a string does not exist, output -1.

A string a is lexicographically smaller than a string b if and only if one of the following holds: 

  * a is a prefix of b, but a ≠ b; 
  * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b. 

Input

The first line contains a single integer T (1 ≤ T ≤ 10 000) — the number of test cases.

The next 2 ⋅ T lines contain the description of test cases. The description of each test case consists of two lines.

The first line of the description contains two integers n and k (1 ≤ k ≤ n ≤ 10^5) — the length of string s and number k respectively.

The second line contains string s consisting of lowercase English letters.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case output in a separate line lexicographically smallest beautiful string of length n, which is greater or equal to string s, or -1 if such a string does not exist.

Example

Input


4
4 2
abcd
3 1
abc
4 3
aaaa
9 3
abaabaaaa


Output


acac
abc
-1
abaabaaab

Note

In the first test case "acac" is greater than or equal to s, and each letter appears 2 or 0 times in it, so it is beautiful.

In the second test case each letter appears 0 or 1 times in s, so s itself is the answer.

We can show that there is no suitable string in the third test case.

In the fourth test case each letter appears 0, 3, or 6 times in "abaabaaab". All these integers are divisible by 3.
import java.util.*;
import java.io.*;
public class Main {
    static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }
    
    public static void sort(int arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(int arr[],int l1,int r1,int l2,int r2) {
        int tmp[]=new int[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    public static void sort(long arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(long arr[],int l1,int r1,int l2,int r2) {
        long tmp[]=new long[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    public static void main(String args[]) throws IOException {
        Scan input=new Scan();
        StringBuilder ans=new StringBuilder("");
        int test=input.scanInt();
        for(int tt=1;tt<=test;tt++) {
            int n=input.scanInt();
            int k=input.scanInt();
            String str=input.scanString();
            
            if(n!=str.length()) {
                for(int i=0;i<n;i++) {
                    ans.append('a');
                }
                ans.append("\n");
                continue;
            }
            
            int cnt[]=new int[26];
            for(int i=0;i<str.length();i++) {
                cnt[str.charAt(i)-'a']++;
            }
            
            boolean done=true;
            
            for(int i=0;i<cnt.length;i++) {
                if(cnt[i]%k!=0) {
                    done=false;
                }
            }
            
            if(done) {
                ans.append(str+"\n");
                continue;
            }
            
            for(int i=n-1;i>=0;i--) {
                cnt[str.charAt(i)-'a']--;
                StringBuilder tmp=check(str,cnt,i,k,n);
                if(tmp.length()==0) {
                    continue;
                }
                ans.append(tmp+"\n");
                done=true;
                break;
            }
            if(!done) {
                ans.append("-1\n");
            }
        }
        System.out.println(ans);
    }
    public static StringBuilder check(String str,int cnt[],int indx,int k,int n) {
        for(int i=str.charAt(indx)+1;i<='z';i++) {
            cnt[i-'a']++;
            int rem=0;
            for(int j=0;j<cnt.length;j++) {
                int tmp=cnt[j]%k;
                if(tmp==0) {
                    continue;
                }
                rem+=k-tmp;
            }
            rem=n-1-indx-rem;
            if(rem<0 || rem%k!=0) {
                cnt[i-'a']--;
                continue;
            }
            
            StringBuilder ans=new StringBuilder("");
            for(int j=0;j<indx;j++) {
                ans.append(str.charAt(j));
            }
            ans.append((char)i);
            for(int j=0;j<rem;j++) {
                ans.append('a');
            }
            for(int j=0;j<cnt.length;j++) {
                int tmp=cnt[j]%k;
                if(tmp==0) {
                    continue;
                }
                tmp=k-tmp;
                for(int m=0;m<tmp;m++) {
                    ans.append((char)(j+'a'));
                }
            }
            return ans;
        }
        return new StringBuilder("");
    }
}
