description: 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.
solution: import java.io.*;
  import java.util.*;
  
  public class Main
  {
  	public static void main(String[] args)throws Exception
  	{
  	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  	    PrintWriter pw=new PrintWriter(System.out);
  	    int t=Integer.parseInt(br.readLine());
  	    while(t-->0)
  	    {
  	        String s[]=(br.readLine()).split(" ");
  	        int n=Integer.parseInt(s[0]);
  	        int k=Integer.parseInt(s[1]);
  	        long x=Long.parseLong(s[2]);
  	        char ar[]=(br.readLine()).toCharArray();
  	        ArrayList<Integer> base=new ArrayList<Integer>();
  	        int ct=0;
  	        for(int i=0;i<n;i++)
  	        {
  	            if(ar[i]=='a')
  	            {
  	                if(ct>0)
  	                {
  	                    base.add(ct*k+1);
  	                }
  	                ct=0;
  	            }
  	            else
  	            {
  	                ct++;
  	            }
  	        }
  	        
  	        if(ct>0)
  	        {
  	            base.add(ct*k+1);
  	        }
  	        ct=0;
  	        
  	        int l=base.size();
  	        
  	        Stack<Long> Bs=new Stack<Long>();
  	        x--;
  	        for(int i=l-1;i>=0;i--)
  	        {
  	            long num=x%(base.get(i));
  	            x/=base.get(i);
  	            Bs.push(num);
  	        }
  	        
  	        ct=0;
  	        ArrayList<Character> ans=new ArrayList<Character>();
  	        for(int i=0;i<n;i++)
  	        {
  	            if(ar[i]=='*')
  	            {
  	                ct++;
  	            }
  	            else
  	            {
  	                if(ct>0)
  	                {
  	                    long num=Bs.pop();
  	                    
  	                    for(int j=0;j<num;j++)
  	                    {
  	                        ans.add('b');
  	                    }
  	                }
  	                ans.add('a');
  	                ct=0;
  	            }
  	        }
  	        
  	        if(ct>0)
  	        {
  	             long num=Bs.pop();
  	            for(int j=0;j<num;j++)
  	            {
  	                ans.add('b');
  	            }
  	        }
  	       
  	        for(int i=0;i<ans.size();i++)
  	        {
  	            pw.print(ans.get(i));
  	        }
  	        pw.println();
  	    }
  	    pw.flush();
  	}
  }
  
  