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

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{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; 
        } 
    } 
//    static int mod = 998244353 ;
//    static int N = 200005;
//    static long factorial_num_inv[] = new long[N+1];
//    static long natual_num_inv[] = new long[N+1];
//    static long fact[] = new long[N+1];
//    static void InverseofNumber() 
//{ 
//    natual_num_inv[0] = 1;
//    natual_num_inv[1] = 1; 
//    for (int i = 2; i <= N; i++) 
//        natual_num_inv[i] = natual_num_inv[mod % i] * (mod - mod / i) % mod; 
//} 
//static void InverseofFactorial() 
//{ 
//    factorial_num_inv[0] = factorial_num_inv[1] = 1; 
  
//    for (int i = 2; i <= N; i++) 
//        factorial_num_inv[i] = (natual_num_inv[i] * factorial_num_inv[i - 1]) % mod; 
//} 
//static long nCrModP(long N, long R) 
//{ 
//    long ans = ((fact[(int)N] * factorial_num_inv[(int)R]) % mod * factorial_num_inv[(int)(N - R)]) % mod; 
//    return ans%mod; 
//}
    //static boolean prime[];
    //static void sieveOfEratosthenes(int n)
    //{
    //    prime = new boolean[n+1];
        
    //    for (int i = 0; i <= n; i++)
    //        prime[i] = true;
 
    //    for (int p = 2; p * p <= n; p++)
    //    {
    //        // If prime[p] is not changed, then it is a
    //        // prime
    //        if (prime[p] == true)
    //        {
    //            // Update all multiples of p
    //            for (int i = p * p; i <= n; i += p)
    //                prime[i] = false;
    //        }
    //    }
 
        
    //}
    
    static int visited[];
	public static void main (String[] args) throws java.lang.Exception
	{
    //    InverseofNumber();
    //    InverseofFactorial();
    //   fact[0] = 1; 
    //   for (long i = 1; i <= 2*100000; i++)
    //   { 
    //       fact[(int)i] = (fact[(int)i - 1] * i) % mod; 
    //   }
    
		FastReader scan = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
        int t = scan.nextInt();
        while(t-->0){   
            int n = scan.nextInt();
            long k = scan.nextLong();
            long x = scan.nextLong();
            String str = scan.next();
            ArrayList<Long> al = new ArrayList<>();
            int i = 0;
            while(i<n){
                if(str.charAt(i)=='*'){
                long count = 0;
                while(i<n && str.charAt(i)=='*'){
                    count++;
                    i++;
                }
                
                al.add(count*k+1);}
                i++;
            }
           //pw.println(al);
            int len = al.size();
            x--;
            ArrayList<Long> ans = new ArrayList<>();
            for(int j=len-1;j>=0;j--){
                ans.add(x%al.get(j));
                x = x/al.get(j);
            }
            int len2 = ans.size();
            int j=len2-1;
            StringBuilder sol = new StringBuilder();
            i= 0;
            while(i<n){
                if(str.charAt(i)=='*'){
                while(i<n && str.charAt(i)=='*'){
                    i++;
                }
                for(int y=0;y<ans.get(j);y++){
                    sol.append('b');
                }
                i--;
                j--;
            }
            else{
                sol.append('a');
            }
            i++;
            }
            pw.println(sol);
            pw.flush();
        }
    }
      
        //static long bin_exp_mod(long a,long n){
            
        //    long res = 1;
            
        //    if(a==0)
        //    return 0;
        //    while(n!=0){
        //        if(n%2==1){
        //            res = ((res)*(a));
        //        }
        //           n = n/2;
        //            a = ((a)*(a));
        //    }
           
        //    return res;
        //}
    //static long bin_exp_mod(long a,long n){
	//    long mod = 1000000007;
	//    long res = 1;
	//    a = a%mod;
	//    if(a==0)
	//    return 0;
	//    while(n!=0){
	//        if(n%2==1){
	//            res = ((res%mod)*(a%mod))%mod;
	//        }
	//           n = n/2;
	//            a = ((a%mod)*(a%mod))%mod;
	//    }
	//    res = res%mod;
	//    return res;
	//}
//   static long gcd(long a,long b){
//       if(a==0)
//       return b;
//       return gcd(b%a,a);
//   }
//   static long lcm(long a,long b){
//       return (a/gcd(a,b))*b;
//   }
}
//class Pair{
//    int x,y;
//    Pair(int x,int y){
//        this.x = x;
//        this.y = y;
//    }
//}
//    public boolean equals(Object obj) {
//        // TODO Auto-generated method stub
//        if(obj instanceof Pair)
//        {
//            Pair temp = (Pair) obj;
//            if(this.x.equals(temp.x) && this.y.equals(temp.y))
//                return true;
//        }
//        return false;
//    }

//    @Override
//    public int hashCode() {
//        // TODO Auto-generated method stub
        
//        return (this.x.hashCode() + this.y.hashCode());        
//    }
//}
//class Compar implements Comparator<Pair>{
//    public int compare(Pair p1,Pair p2){
//        if(p1.y>p2.y)
//        return 1;
//        else
//        return -1;
//    }
//}