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.
//package credit;


import javax.swing.plaf.multi.MultiTableHeaderUI;
import java.io.*;
import java.net.CookieHandler;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static boolean v[];
    static int ans[];
    int size[];
    static int count=0;
    static int dsu=0;
    static int c=0;
    static int e9=1000000007;
    int min=Integer.MAX_VALUE;
    int max=Integer.MIN_VALUE;
    long max1=Long.MIN_VALUE;
    long min1=Long.MAX_VALUE;
    boolean aBoolean=true;
    boolean y=false;
    long m=0;
    static boolean t1=false;
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    int parent[];
    int rank[];
    int n=0;
    ArrayList<ArrayList<Integer>> arrayLists;
    boolean v1[];
    static boolean t2=false;
    boolean r=false;
    int fib[];
    int fib1[];
    int ind[];
    int min3=Integer.MAX_VALUE;
    int k=0;
    public static void main(String[] args) throws IOException {
        Main g = new Main();
        g.go();
    }
    public void go() throws IOException {
        FastReader scanner = new FastReader();
//            Scanner scanner = new Scanner(System.in);
//            BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
//            String s;
        PrintWriter printWriter = new PrintWriter(System.out);
        int t =scanner.nextInt();
        while(t-->0) {
            int n=scanner.nextInt();
            k=scanner.nextInt();
            String s=scanner.next();
            if(n%k!=0){
                printWriter.println(-1);
                continue;
            }
            char ans[]=s.toCharArray();
            fib=new int[26];
            int sum=0;
            for (int i = 0; i < s.length(); i++) {
                fib[s.charAt(i)-'a']++;
            }
            for (int i = 0; i < 26; i++) {
                sum+=(check(fib[i]));
            }
            if(sum==0){
                printWriter.println(s);
            }else{
                outer:for (int i =n-1; i>=0; i--) {
                    sum-=(check(fib[ans[i]-'a']));
                    fib[ans[i]-'a']--;
                    sum+=(check(fib[ans[i]-'a']));
                    for (int j =ans[i]-'a'+1; j <26; j++) {
                        int sum2=sum;
                        sum-=(check(fib[j]));
                        fib[j]++;
                        sum+=(check(fib[j]));
                        if(sum+i<n){
                            for (int k = 0; k < i; k++) {
                                printWriter.print(ans[k]+"");
                            }
                            printWriter.print((char)('a'+j));
                            ArrayList<Character> arrayList=new ArrayList<>();
                            for (int k = 0; k < 26; k++) {
                                if(check(fib[k])>0){
                                    int u1=check(fib[k]);
                                    while(u1>0){
                                        arrayList.add((char)('a'+k));
                                        u1--;
                                    }
                                }
                            }
                            while (arrayList.size()+i+1<n){
                                arrayList.add('a');
                            }
                            Collections.sort(arrayList);
                            for (int k = 0; k < arrayList.size(); k++) {
                                printWriter.print(arrayList.get(k)+"");
                            }
                            printWriter.println();
                            break outer;
                        }
                        sum=sum2;
                        fib[j]--;
                    }
                }
            }
        }
        printWriter.flush();
    }
    static final int mod=1_000_000_007;
    public int check(int u){
        return (k-u%k)%k;
    }
    public long mul(long a, long b) {
        return a*b;
    }
    public long fact(int x) {
        long ans=1;
        for (int i=2; i<=x; i++) ans=mul(ans, i);
        return ans;
    }
    public long fastPow(long base, long exp) {
        if (exp==0) return 1;
        long half=fastPow(base, exp/2);
        if (exp%2==0) return mul(half, half);
        return mul(half, mul(half, base));
    }
    public long modInv(long x) {
        return fastPow(x, mod-2);
    }
    public long nCk(int n, int k) {
        return mul(fact(n), mul(modInv(fact(k)), modInv(fact(n-k))));
    }
    //    public void sieve(int n){
//        fib=new int[n+1];
//        fib[1]=-1;
//        fib[0]=-1;
//        for (int i =2; i*i<=n; i++) {
//            if(fib[i]==0)
//            for (int j =i*i; j <=n; j+=i){
//                fib[j]=-1;
////                System.out.println("l");
//            }
//        }
//    }
    public void parent(int n){
        parent=new int[n+1];
        size=new int[n+1];
        rank=new int[n+1];
        for (int i = 0; i <=n; i++) {
            parent[i]=i;
            rank[i]=0;
            size[i]=1;
        }
    }
    public void union(int i,int j){
        int root1=find(i);
        int root2=find(j);
//            if(root1 != root2) {
//                parent[root2] = root1;
////                sz[a] += sz[b];
//            }
        if(root1==root2){
            return;
        }
        if(rank[root1]>rank[root2]){
            parent[root2]=root1;
            size[root1]+=size[root2];
        }
        else if(rank[root1]<rank[root2]){
            parent[root1]=root2;
            size[root2]+=size[root1];
        }
        else{
            parent[root2]=root1;
            rank[root1]+=1;
            size[root1]+=size[root2];
        }
    }
    public int find(int p){
        if(parent[p]!=p){
            if(parent[p]==-1){
                return parent[p];
            }
            parent[p]=find(parent[p]);
        }
        return parent[p];
    }
    public double dist(double x1,double y1,double x2,double y2){
        double e=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
        double e1=Math.sqrt(e);
        return e1;
    }
    public void make(int p){
        parent[p]=p;
        rank[p]=1;
    }
    Random rand = new Random();
    public void sort(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            int j = rand.nextInt(i + 1);
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a, 0, n);
    }
    public long gcd(long a,long b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }
    public void dfs(ArrayList<Integer> arrayList){
        for (int i = 0; i < arrayList.size(); i++) {
            if(v1[arrayList.get(i)]==false){
                v1[arrayList.get(i)]=true;
                dfs(arrayLists.get(i));
            }
        }
    }
    public double fact(double h){
        double sum=1;
        while(h>=1){
            sum=(sum%e9)*(h%e9);
            h--;
        }
        return sum%e9;
    }
    public long primef(double r){
        long c=0;
        long ans=1;
        while(r%2==0){
            c++;
            r=r/2;
        }
        if(c>0){
            ans*=2;
        }
        c=0;
//            System.out.println(ans+" "+r);
        for (int i = 3; i <=Math.sqrt(r) ;i+=2) {
            while(r%i==0){
//                    System.out.println(i);
                c++;
                r=r/i;
            }
            if(c>0){
                ans*=i;
            }
            c=0;
        }
        if(r>2){
            ans*=r;
        }
        return ans;
    }
    public long divisor(double r){
        long c=0;
        for (int i = 1; i <=Math.sqrt(r); i++) {
            if(r%i==0){
                if(r/i==i){
                    c++;
                }
                else{
                    c+=2;
                }
            }
        }
        return c;
    }
}
class Pair{
    int x;
    char y;
    double z;
    public Pair(int x,char y){
        this.x=x;
        this.y=y;
    }

   // @Override
//    public int hashCode() {
//        int hash =37;
//        return this.x * hash + this.y;
//    }
//    @Override
//    public boolean equals(Object o1){
//        if(o1==null||o1.getClass()!=this.getClass()){
//            return false;
//        }
//        Pair o=(Pair)o1;
//        if(o.x==this.x&&o.y==this.y){
//            return true;
//        }
//        return false;
//    }
}
class Sorting implements Comparator<Pair> {
    public int compare(Pair p1,Pair p2){
            return Double.compare(p1.x, p2.x);
        }
    }
//class Pair1{
//    int x;
//    int y;
//    double z;
//    public Pair1(Pair p1,double c){
//        this.x=p1.x;
//        this.y=p1.y;
//        z=c;
//    }
//
//    @Override
//    public int hashCode() {
//        int hash =37;
//        return this.x * hash + this.y;
//    }
//    public double dist(double x1,double y1,double x2,double y2){
//        double e=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
//        double e1=Math.sqrt(e);
//        return e1;
//    }
//
//    @Override
//    public boolean equals(Object o1){
//        if(o1==null||o1.getClass()!=this.getClass()){
//            return false;
//        }
//        Pair1 o=(Pair1)o1;
//        if(o.x==this.x&&o.y==this.y){
//            return true;
//        }
//        return false;
//    }
//}
//class Sorting implements Comparator<Pair1> {
//    public int compare(Pair1 p1,Pair1 p2){
////        if(p1.x==p2.x){
////            return -1*Double.compare(p1.y,p2.y);
////        }
////        else {
//        return Double.compare(p1.z, p2.z);
//        // }
//    }
//
//}
