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.awt.*;
import java.awt.desktop.SystemEventListener;
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.locks.ReadWriteLock;


public class Main {

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Reader.nextInt();
        while ( t > 0){
            long n = Reader.nextLong();
            long k = Reader.nextLong();
            long x = Reader.nextLong();
            char [] string = Reader.next().toCharArray();
            if ( n == 1){
                System.out.println("a");
            }
            else {
                ArrayList<Node> q = new ArrayList<>();
                long last = -1;
                int i = 0;
                long count = 0;
                while (i < n) {
                    if (last != -1) {
                        if (string[i] == '*'){
                            if ( last == 0){
                                count++;
                            }
                            else{
                                last = 0;
                                count =1;
                            }
                        }
                        else{
                            if ( last == 0){
                                q.add(new Node(count,0));

                            }
                            q.add(new Node(1,1));
                            count =0;
                            last = 1;

                        }
                    }
                    else {
                        if (string[i] == '*') {
                            last = 0;
                            count = 1;
                        } else {
                            last = 1;
                            count = 0;
                            q.add(new Node(1,1));
                        }

                    }
                    i++;
                }
                if ( count != 0){
                    q.add(new Node(count,0));
                }
                i = 0;
                while ( i < q.size()){
                    Node curr = q.get(i);
                    if ( curr.ch == 0){
                        curr.k = ((curr.k)*k)+1;
                    }
                    i++;
                }
                i = 0;
                ArrayList<Long> answer = new ArrayList<>();
                while ( i < q.size()){
                    Node curr = q.get(i);
                    if ( curr.ch == 0){
                        if (i == q.size()-1){
                            answer.add(x - 1);
                        }
                        else{
                            int j = i+1;
                            long totalPossible = 1;
                            while ( j < q.size()){
                                Node v = q.get(j);
                                if ( v.ch == 0){
                                    totalPossible = totalPossible*v.k;
                                }
                                j++;
                            }
                            long d = x/totalPossible;
                            long r = x%totalPossible;
                            if ( r == 0){
                                answer.add(d-1);
                                x = x - ((d-1)*totalPossible);
                            }
                            else{
                                answer.add(d);
                                x = x - (d*totalPossible);
                            }



                        }
                    }
                    else{
                        answer.add((long)-1);
                    }
                    i++;
                }
                i = 0;
                String ans = "";
                while ( i < answer.size()){
                    long v  = answer.get(i);
                    if ( v == -1){
                        output.write("a");
                    }
                    else{
                        while ( v > 0){
                            output.write("b");
                            v--;
                        }
                    }

                    i++;
                }
                output.write('\n');
            }
            t--;
        }
        output.flush();


    }
    public static int sub(int a, int b){
       int half = b/2;
       if ( b%2 == 0){
           if ( a < half){
               return 1;
           }
           else{
               return -1;
           }
       }
       else{
           if ( a<= half){
               return 1;
           }
           else{
               return -1;
           }
       }
    }


    private static int bs(int low,int high,int[] array,int find){
        if ( low <= high ){
            int  mid = low + (high-low)/2;
            if ( array[mid] > find){
                high = mid -1;
                return bs(low,high,array,find);
            }
            else if ( array[mid] < find){
                low = mid+1;
                return bs(low,high,array,find);
            }
            return mid;
        }
        return -1;
    }

    private static long max(long a, long b) {
        return  Math.max(a,b);
    }

    private static int min(int a,int b){
        return  Math.min(a,b);
    }

    public static long modularExponentiation(long a,long b,long mod){
        if ( b == 1){
            return a;
        }
        else{
            long ans = modularExponentiation(a,b/2,mod)%mod;
            if ( b%2 == 1){
                return (a*((ans*ans)%mod))%mod;
            }

            return ((ans*ans)%mod);
        }
    }

    public static long sum(long n){
        return  (n*(n+1))/2;
    }
    public static long abs(long a){
        return a < 0 ? (-1*a) : a;
    }
    public static long gcd(long a,long b){
        if ( a == 0){
            return b;
        }
        else{
            return gcd(b%a,a);
        }
    }


}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;


    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {

            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

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

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

    static long nextLong() throws IOException{
        return Long.parseLong(next());
    }
}
/*
class NComparator implements Comparator<Node>{
    @Override
    public int compare(Node o1, Node o2) {
        if ( o2.position > o1.position){
            return 1;
        }
        else if ( o2.position < o1.position){
            return -1;
        }
        else{
            if ( o2.time < o1.time){
                return 1;
            }
            else if ( o2.time > o2.time){
                return -1;
            }
            else{
                return 0;
            }
        }
    }
}


class DComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if ( o2 > o1){
            return 1;
        }
        else if ( o2 < o1){
            return -1;
        }
        else{
            return 0;
        }
    }
}

*/
class Node{
    long k;
    long ch;

    Node(long K,long C){
        k = K;
        ch = C;
    }

}