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.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
import java.io.*;
public class Main {
    // Graph
    // prefix sums
    //inputs
    public static void main(String args[])throws Exception{
        Input sc=new Input();
        precalculates p=new precalculates();
        StringBuilder sb=new StringBuilder();
        int t=sc.readInt();
        for(int f=0;f<t;f++){
            long d[]=sc.readArrayLong();
            String str=sc.readString();
            int n=(int)d[0];
            long k=d[1],x=d[2];
            StringBuilder s[]=new StringBuilder[(int)x];
            StringBuilder ans=new StringBuilder();
            for(int i=0;i<x;i++){
                s[i]=new StringBuilder();
            }
            for(int i=0;i<n;i++){
                if(str.charAt(i)=='*'){
                    for(int j=0;j<k;j++){
                        s[0].append("*");
                    }
                }else
                    s[0].append("a");
            }
            ans=new StringBuilder(s[0]);
            System.out.println("  "+ans);
            int ind=ans.length()-1;
            int count=1;
            for(int i=1;i<x;i++){
                if(ans.charAt(ind)=='a'){
                    //count++;
                    break;
                }else{
                    count++;
                    s[i]=new StringBuilder(ans.substring(0,ind)+"b"+s[i-1].substring(ind+1));
                    ind--;
                }
                System.out.println(i+"\t"+s[i]+" "+count);
            }
            for(int i=count;i<x;i++){
                int temp=(i)/count;
                if(ans.charAt(ind-temp)=='a'){
                    ind=ind-temp;
                    while(ans.charAt(ind)=='a'){
                        ind--;
                    }
                    ind++;
                    count=i;
                }
                temp=(i)/count;
                //System.out.println(ind+" "+s[3]+" "+count);
                s[i]=new StringBuilder(ans.substring(0,ind-temp)+"b"+s[i-(count)].substring(ind-temp+1));
                System.out.println(i+"\t"+s[i]+" "+count);
            }
            for(int i=0;i<ans.length();i++){
                if(s[(int)x-1].charAt(i)!='*'){
                    sb.append(s[(int)x-1].charAt(i));
                }
            }
            sb.append("\n");

        }
        System.out.print(sb);
    }
}
class Input{
    BufferedReader br;
    StringTokenizer st;
    Input(){
        br=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
    }
    public int[] readArray() throws Exception{
        st=new StringTokenizer(br.readLine());
        int a[]=new int[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        return a;
    }
    public long[] readArrayLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        long a[]=new long[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Long.parseLong(st.nextToken());
        }
        return a;
    }
    public int readInt() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
    public long readLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Long.parseLong(st.nextToken());
    }
    public String readString() throws Exception{
        return br.readLine();
    }
    public int[][] read2dArray(int n,int m)throws Exception{
        int a[][]=new int[n][m];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                a[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        return a;
    }
}
class precalculates{
    public long gcd(long p, long q) {
        if (q == 0) return p;
        else return gcd(q, p % q);
    }
    public int[] prefixSumOneDimentional(int a[]){
        int n=a.length;
        int dp[]=new int[n];
        for(int i=0;i<n;i++){
            if(i==0)
                dp[i]=a[i];
            else
                dp[i]=dp[i-1]+a[i];
        }
        return dp;
    }
    public int[] postSumOneDimentional(int a[]) {
        int n = a.length;
        int dp[] = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1)
                dp[i] = a[i];
            else
                dp[i] = dp[i + 1] + a[i];
        }
        return dp;
    }
    public int[][] prefixSum2d(int a[][]){
        int n=a.length;int m=a[0].length;
        int dp[][]=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=a[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            }
        }
        return dp;
    }
    public long pow(long a,long b){
        long mod=1000000007;
        long ans=1;
        if(b<=0)
            return 1;
        if(b%2==0){
            ans=pow(a,b/2)%mod;
            return ((ans%mod)*(ans%mod))%mod;
        }else{
            ans=pow(a,b-1)%mod;
            return ((a%mod)*(ans%mod))%mod;
        }
    }

}
class GraphInteger{
    HashMap<Integer,vertex> vtces;
    class vertex{
        HashMap<Integer,Integer> children;
        public vertex(){
            children=new HashMap<>();
        }
    }
    public GraphInteger(){
        vtces=new HashMap<>();
    }
    public void addVertex(int a){
        vtces.put(a,new vertex());
    }
    public void addEdge(int a,int b,int cost){
        if(!vtces.containsKey(a)){
            vtces.put(a,new vertex());
        }
        if(!vtces.containsKey(b)){
            vtces.put(b,new vertex());
        }
        vtces.get(a).children.put(b,cost);
//        vtces.get(b).children.put(a,cost);
    }
    public boolean isCyclicDirected(){
        boolean isdone[]=new boolean[vtces.size()+1];
        boolean check[]=new boolean[vtces.size()+1];
        for(int i=1;i<=vtces.size();i++) {
            if (!isdone[i] && isCyclicDirected(i,isdone, check)) {
                return true;
            }
        }
        return false;
    }
    private boolean isCyclicDirected(int i,boolean isdone[],boolean check[]){
        if(check[i])
            return true;
        if(isdone[i])
            return false;
        check[i]=true;
        isdone[i]=true;
        Set<Integer> set=vtces.get(i).children.keySet();
        for(Integer ii:set){
            if(isCyclicDirected(ii,isdone,check))
                return true;
        }
        check[i]=false;
        return false;
    }
}
class union_find {
    int n;
    int[] sz;
    int[] par;

    union_find(int nval) {
        n = nval;
        sz = new int[n + 1];
        par = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int x) {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    boolean find(int a, int b) {
        return root(a) == root(b);
    }

    int union(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra == rb)
            return 0;
        if(a==b)
            return 0;
        if (sz[a] > sz[b]) {
            int temp = ra;
            ra = rb;
            rb = temp;
        }
        par[ra] = rb;
        sz[rb] += sz[ra];
        return 1;
    }
}

/*
* * a * * a * *
2 2 2 1 1 1 0 0

1  * * a * * a * *
2  * * a * * a * b
3  * * a * * a b b
4  * * a * b a * *
5  * * a * b a * b
6  * * a * b a b b
7  * * a b b a * *
8  * * a b b a * b
9  * * a b b a b b
10 * b a * * a * *
11 baab
12 baabb
13 baba
14 babab
15 bababb
16 babba
17 babbab
18 babbabb
19 bbaa
20
 */





