You are given an integer k and a string s that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk).

Each asterisk should be replaced with several (from 0 to k inclusive) lowercase Latin letters 'b'. Different asterisk can be replaced with different counts of letter 'b'.

The result of the replacement is called a BA-string.

Two strings a and b are different if they either have different lengths or there exists such a position i that a_i ≠ b_i.

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. 



Now consider all different BA-strings and find the x-th lexicographically smallest of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 2000) — the number of testcases.

The first line of each testcase contains three integers n, k and x (1 ≤ n ≤ 2000; 0 ≤ k ≤ 2000; 1 ≤ x ≤ 10^{18}). n is the length of string s.

The second line of each testcase is a string s. It consists of n characters, each of them is either 'a' (a lowercase Latin letter) or '*' (an asterisk).

The sum of n over all testcases doesn't exceed 2000. For each testcase x doesn't exceed the total number of different BA-strings. String s contains at least one character 'a'.

Output

For each testcase, print a single string, consisting only of characters 'b' and 'a' (lowercase Latin letters) — the x-th lexicographically smallest BA-string.

Example

Input


3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***


Output


abb
abba
babbbbbbbbb

Note

In the first testcase of the example, BA-strings ordered lexicographically are: 

  1. a
  2. ab
  3. abb
  4. abbb
  5. abbbb



In the second testcase of the example, BA-strings ordered lexicographically are: 

  1. aa
  2. aba
  3. abba



Note that string "aba" is only counted once, even though there are two ways to replace asterisks with characters 'b' to get it.
2
55 982 31372
a*a*aa*aa*a*aa*aa*aaa*aaaaa*a*aa*aaaaa*aaaaa*aa*a*a*a*a
63 9 10946
*aaaaa*aa*a*a*aa*aaaa*a*aa*a*a*aaaa*aaaaa*a*a*aaa*aa*aaa*a*a*aa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabbbbbbbbbabbbbabbbbbaa

        import java.beans.DesignMode;
        import java.io.BufferedReader;
        import java.io.FileInputStream;
        import java.io.FileNotFoundException;
        import java.io.IOException;
        import java.io.InputStreamReader;
        import java.util.*;
        import java.util.concurrent.LinkedBlockingDeque;
        import java.util.concurrent.CompletableFuture.AsynchronousCompletionTask;

        import org.xml.sax.ErrorHandler;

        import java.io.PrintStream;
        import java.io.PrintWriter;
        import java.io.DataInputStream;

        public class Solution {
                //TEMPLATE -------------------------------------------------------------------------------------
                public static boolean Local(){
                    try{ 
                        return System.getenv("LOCAL_SYS")!=null;
                    }catch(Exception e){
                        return false;
                    }
                }   

                public static boolean LOCAL;

                static class FastScanner {

                        BufferedReader br;
                        StringTokenizer st ;

                        FastScanner(){
                            br =  new BufferedReader(new InputStreamReader(System.in));
                            st = new StringTokenizer("");
                        }

                        FastScanner(String file) {

                            try{
                                br =  new BufferedReader(new InputStreamReader(new FileInputStream(file)));
                                st = new StringTokenizer("");
                            }catch(FileNotFoundException e) {
                                // TODO Auto-generated catch block
                                System.out.println("file not found");
                                e.printStackTrace();
                            }
                            
                        }
                        String next() {
                            while (!st.hasMoreTokens())
                                try {
                                    st = new StringTokenizer(br.readLine());
                                } catch (IOException e) {
                                }
                            return st.nextToken();
                        }

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

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

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

                        String readLine() throws IOException{
                            return br.readLine();
                        }
                    }
                                        
                static class Pair<T,X> {

                    T first;
                    X second;
                    
                    Pair(T first,X second){
                        this.first = first;
                        this.second = second;
                    }

                    @Override
                    public int hashCode(){
                        return Objects.hash(first,second);
                    }

                    @Override
                    public boolean equals(Object obj){
                        return obj.hashCode() == this.hashCode();
                    }

                }

            
            static PrintStream debug = null;      
            static long mod = (long)(Math.pow(10,9) + 7); 
        //TEMPLATE -------------------------------------------------------------------------------------END//
            public static void main(String[] args) throws Exception {
                
                FastScanner s = new FastScanner();
                LOCAL = Local();
                //PrintWriter pw = new PrintWriter(System.out);
                if(LOCAL){
                    s = new FastScanner("src/input.txt");
                    
                    PrintStream o = new PrintStream("src/sampleout.txt");
                    debug = new PrintStream("src/debug.txt");
                    System.setOut(o);
                //  pw = new PrintWriter(o);
                } long mod = 1000000007;

            
                int tcr = s.nextInt();                         
                StringBuilder sb = new StringBuilder();
            

                for(int tc=0;tc<tcr;tc++){
                    int n = s.nextInt();
                    int k = s.nextInt();
                    long x = s.nextLong();
                    x--;
                    List<int[]> segments = new ArrayList<>();
                    char arr[] = s.next().toCharArray();
                    int index = 0;
                    while(index  < arr.length){
                        if(arr[index] == 'a'){
                            int cnt = 0;
                            while(index < arr.length && arr[index] == 'a'){
                                index++;
                                cnt++;
                            }
                            segments.add(new int[]{0,cnt});
                        }else{
                            int cnt = 0;
                            while(index < arr.length && arr[index] == '*'){
                                index++;
                                cnt++;
                            }
                            segments.add(new int[]{1,(k*cnt) + 1});
                        }
                    }

                    //dbg(debug,segments);
                    int cnt[] = new int[segments.size()];

                    for(int i=segments.size()-1;i>=0;i--){
                        if(segments.get(i)[0] == 1){
                            cnt[i] = (int)(x % segments.get(i)[1]);
                            x = x / segments.get(i)[1];    
                        }
                        if(x == 0l){break;}
                    }

                    //dbg(debug,cnt);
                    for(int i=0;i<segments.size();i++){
                        if(segments.get(i)[0] == 0){
                            for(int j=0;j<segments.get(i)[1];j++){sb.append('a');}
                        }else{
                            for(int j=0;j<cnt[i];j++){
                                sb.append('b');
                            }
                        }
                    }

                    sb.append('\n');


                }

                print(sb.toString());
            }

            public static List<int[]> print_prime_factors(int n){
            
                List<int[]> list = new ArrayList<>();
                
                for(int i=2;i<=(int)(Math.sqrt(n));i++){

                    if(n % i == 0){
                        
                        int cnt = 0;
                        
                        while( (n % i) == 0){
                            n = n/i;
                            cnt++;
                        }

                        list.add(new int[]{i,cnt});
                    }
                }

                if(n!=1){
                    list.add(new int[]{n,1});
                }

                return list;
            }

            public static List<int[]> prime_factors(int n,List<Integer> sieve){
                List<int[]> list = new ArrayList<>();
                int index = 0;
                while(n > 1 && sieve.get(index) <= Math.sqrt(n)){
                    int curr = sieve.get(index);
                    int cnt = 0;
                    while((n % curr) == 0){
                        n = n/curr;
                        cnt++;
                    }
                    if(cnt >= 1){
                        list.add(new int[]{curr,cnt});
                    }
                    index++;
                }
                if(n > 1){
                    list.add(new int[]{n,1});
                }
                return list;
            }

            public static boolean inRange(int r1,int r2,int val){
                return ((val >= r1) && (val <= r2));
            }

            static int len(long num){
                return Long.toString(num).length();
            }

            static long mulmod(long a, long b,long mod)
            {
                long ans = 0l;
                
                while(b > 0){
                    long curr = (b & 1l);
                    if(curr == 1l){
                        ans = ((ans % mod) + a) % mod;
                    }
                    
                    a = (a + a) % mod;

                    b = b >> 1;
                }

                return ans;
            }


            public static void dbg(PrintStream ps,Object... o) throws Exception{
                if(ps == null){
                    return;
                }
                Debug.dbg(ps,o);
            }

            public static long modpow(long num,long pow,long mod){

                long val = num;
                long ans = 1l;

                while(pow > 0l){
                    
                    long bit = pow & 1l;

                    if(bit == 1){
                        ans = (ans * (val%mod))%mod;
                    }

                    val = (val * val) % mod;
                    pow = pow >> 1;
                }

                return ans;

            }

            public static long pow(long num,long pow){

                long val = num;
                long ans = 1l;

                while(pow > 0l){
                    
                    long bit = pow & 1l;

                    if(bit == 1){
                        ans = (ans * (val));
                    }

                    val = (val * val);
                    pow = pow >> 1;
                }

                return ans;
            }
            
            public static char get(int n){
                return (char)('a' + n);
            }

            public static long[] sort(long arr[]){
                List<Long> list = new ArrayList<>();
                for(long n : arr){list.add(n);}
                Collections.sort(list);
                for(int i=0;i<arr.length;i++){
                    arr[i] = list.get(i);
                }
                return arr;
            }

            public static int[] sort(int arr[]){
                List<Integer> list = new ArrayList<>();
                for(int n : arr){list.add(n);}
                Collections.sort(list);
                for(int i=0;i<arr.length;i++){
                    arr[i] = list.get(i);
                }
                return arr;
            }

            // return the (index + 1)
            // where index is the pos of just smaller element
            // i.e count of elemets strictly less than num
            public static int justSmaller(long arr[],long num){
                //  System.out.println(num+"@");
                int st = 0;
                int e = arr.length - 1;

                int ans = -1;

                while(st <= e){

                    int mid = (st + e)/2;

                    if(arr[mid] >= num){
                        e = mid - 1;
                    }else{
                        ans = mid;
                        st = mid + 1;
                    }

                }


                return ans + 1;

            }
            public static int justSmaller(int arr[],int num){
                //  System.out.println(num+"@");
                int st = 0;
                int e = arr.length - 1;

                int ans = -1;

                while(st <= e){

                    int mid = (st + e)/2;

                    if(arr[mid] >= num){
                        e = mid - 1;
                    }else{
                        ans = mid;
                        st = mid + 1;
                    }

                }


                return ans + 1;

            }
            
            //return (index of just greater element)
            //count of elements smaller than or equal to num

            public static int justGreater(long arr[],long num){
                int st = 0;
                int e = arr.length - 1;

                int ans = arr.length;

                while(st <= e){
                    
                    int mid = (st + e)/2;

                    if(arr[mid] <= num){
                        st = mid + 1;
                    }else{
                        ans = mid;
                        e = mid - 1;
                    }
                }

                return ans;

            }

            public static int justGreater(int arr[],int num){
                int st = 0;
                int e = arr.length - 1;

                int ans = arr.length;

                while(st <= e){
                    
                    int mid = (st + e)/2;

                    if(arr[mid] <= num){
                        st = mid + 1;
                    }else{
                        ans = mid;
                        e = mid - 1;
                    }
                }

                return ans;

            }

            

            public static void println(Object obj){
                System.out.println(obj.toString());
            }

            public static void print(Object obj){
                System.out.print(obj.toString());
            }

            public static int gcd(int a,int b){
                if(b == 0){return a;}
                return gcd(b,a%b);
            }

            public static long gcd(long a,long b){
                if(b == 0l){
                    return a;
                }

                return gcd(b,a%b);
            }

            public static int find(int parent[],int v){
                if(parent[v] == v){
                    return v;
                }
                
                return parent[v] = find(parent, parent[v]);
            }



            public static List<Integer> sieve(){
            
                    List<Integer> prime = new ArrayList<>();

                    int arr[] = new int[1000001];

                Arrays.fill(arr,1);

                arr[1] = 0;
                arr[2] = 1;

                for(int i=2;i<1000001;i++){
                    
                    if(arr[i] == 1){
                        
                        prime.add(i);

                        for(long j = (i*1l*i);j<1000001;j+=i){
                            arr[(int)j] = 0;
                        }
                    }
                }

                return prime;
            }

            static boolean isPower(long n,long a){
                
                long log = (long)(Math.log(n)/Math.log(a));

                long power = (long)Math.pow(a,log);

                if(power == n){return true;}

                return false;
            }


            private static int mergeAndCount(int[] arr, int l,int m, int r)
            {
                // Left subarray
                int[] left =  Arrays.copyOfRange(arr, l, m + 1);

                // Right subarray
                int[] right = Arrays.copyOfRange(arr, m + 1, r + 1);

                int i = 0, j = 0, k = l, swaps = 0;

                while (i < left.length && j < right.length) {
                    if (left[i] <= right[j])
                        arr[k++] = left[i++];
                    else {
                        arr[k++] = right[j++];
                        swaps += (m + 1) - (l + i);
                    }
                }
                while (i < left.length)
                    arr[k++] = left[i++];
                while (j < right.length)
                    arr[k++] = right[j++];
                return swaps;
            }

            // Merge sort function
            private static int mergeSortAndCount(int[] arr, int l,int r)
            {

                // Keeps track of the inversion count at a
                // particular node of the recursion tree
                int count = 0;

                if (l < r) {
                    int m = (l + r) / 2;

                    // Total inversion count = left subarray count
                    // + right subarray count + merge count

                    // Left subarray count
                    count += mergeSortAndCount(arr, l, m);

                    // Right subarray count
                    count += mergeSortAndCount(arr, m + 1, r);

                    // Merge count
                    count += mergeAndCount(arr, l, m, r);
                }

                return count;
            }

            static class Debug{
                //change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
                public static final boolean LOCAL = System.getProperty("ONLINE_JUDGE")==null;

                

                private static <T> String ts(T t) {
                    if(t==null) {
                        return "null";
                    }
                    try {
                        return ts((Iterable<T>) t);
                    }catch(ClassCastException e) {
                        if(t instanceof int[]) {
                            String s = Arrays.toString((int[]) t);
                            return "{"+s.substring(1, s.length()-1)+"}\n";
                        }else if(t instanceof long[]) {
                            String s = Arrays.toString((long[]) t);
                            return "{"+s.substring(1, s.length()-1)+"}\n";
                        }else if(t instanceof char[]) {
                            String s = Arrays.toString((char[]) t);
                            return "{"+s.substring(1, s.length()-1)+"}\n";
                        }else if(t instanceof double[]) {
                            String s = Arrays.toString((double[]) t);
                            return "{"+s.substring(1, s.length()-1)+"}\n";
                        }else if(t instanceof boolean[]) {
                            String s = Arrays.toString((boolean[]) t);
                            return "{"+s.substring(1, s.length()-1)+"}\n";
                        }
                        try {
                            return ts((Object[]) t);
                        }catch(ClassCastException e1) {
                            return t.toString();
                        }
                    }
                }
                private static <T> String ts(T[] arr) {
                    StringBuilder ret = new StringBuilder();
                    ret.append("{");
                    boolean first = true;
                    for(T t: arr) {
                        if(!first) {
                            ret.append(", ");
                        }
                        first = false;
                        ret.append(ts(t));
                    }
                    ret.append("}");
                    return ret.toString();
                }
                private static <T> String ts(Iterable<T> iter) {
                    StringBuilder ret = new StringBuilder();
                    ret.append("{");
                    boolean first = true;
                    for(T t: iter) {
                        if(!first) {
                            ret.append(", ");
                        }
                        first = false;
                        ret.append(ts(t));
                    }
                    ret.append("}\n");
                    return ret.toString();
                }
                public static void dbg(PrintStream ps,Object... o) throws Exception {
                    if(LOCAL) {
                        System.setErr(ps);
                        System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [\n");
                        for(int i = 0; i<o.length; i++) {
                            if(i!=0) {
                                System.err.print(", ");
                            }
                            System.err.print(ts(o[i]));
                        }
                        System.err.println("]");
                    }
                }
            }

        }