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.BufferedReader;
  import java.io.BufferedWriter;
  import java.io.File;
  import java.io.FileInputStream;
  import java.io.FileOutputStream;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.InputStreamReader;
  import java.io.OutputStream;
  import java.io.OutputStreamWriter;
  import java.io.PrintWriter;
  import java.io.StreamTokenizer;
  import java.math.BigInteger;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.PriorityQueue;
  import java.util.Queue;
  import java.util.Random;
  import java.util.Scanner;
  import java.util.Stack;
  import java.util.StringTokenizer;
  import java.util.TreeMap;
  import java.util.TreeSet;
  public class Main {
  	public static void main(String[]args) throws IOException {
  		new Main().run();
  	}
  	File input=new File("D:\\test\\input.txt");
  	void run() throws IOException{
  //	  new solve().setIO(input, System.out).run();
  		new solve().setIO(System.in, System.out).run();
  	}
  	class solve extends ioTask{
  		int t,n,k,i,j;
  		char[]ch;
  		int[]sta=new int[2005];
  		long[]cnt=new long[2005];
  		long x;
  		void run() throws IOException {
  			t=in.in();
  			while(t-->0)
  			{
  				n=in.in();
  				k=in.in();
  				x=in.inl()-1;
  				ch=('a'+in.ins()).toCharArray();
  				sta[0]=0;
  				char pre='a';
  				{
  					int cnt=0;
  					for(char c:ch)
  					{
  						if(pre==c)cnt++;
  						else
  						{
  							pre=c;
  							sta[++sta[0]]=cnt;
  							cnt=1;
  						}
  					}
  					sta[++sta[0]]=cnt;
  				}
  				long ll=1;
  				for(i=sta[0]%2==0?sta[0]:sta[0]-1;i>1;i-=2) {
  					cnt[i]=ll;
  					ll*=sta[i]*k+1;
  					if(ll<0||ll>x) {
  						i-=2;
  						break;
  					}
  				}
  //				for(int i=1;i<=sta[0];i++)
  //				{
  //					out.print(cnt[i]+" ");
  //				}
  //				out.println();
  				i+=2;
  				for(j=i;j>1;j-=2) {
  					sta[j]=0;
  				}
  				for(;i<=sta[0];i+=2) {
  					sta[i]=(int) (x/cnt[i]);
  					x%=cnt[i];
  				}
  				sta[1]--;
  				for(i=1;i<=sta[0];i++)
  				{
  					if(i%2==1) {
  						while(sta[i]-->0)out.print('a');
  					}else {
  						while(sta[i]-->0)out.print('b');
  					}
  				}
  				out.println();
  			}
  			out.close();
  		}
  	}
  	class In{
  		private StringTokenizer in=new StringTokenizer("");
  		private InputStream is;
  		private BufferedReader bf;
  		public In(File file) throws IOException {
  			is=new FileInputStream(file);
  			init();
  		}
  		public In(InputStream is) throws IOException
  		{
  			this.is=is;
  			init();
  		}
  		private void init() throws IOException {
  			bf=new BufferedReader(new InputStreamReader(is));
  		}
  		boolean hasNext() throws IOException {
  			return in.hasMoreTokens()||bf.ready();
  		}
  		String ins() throws IOException {
  			while(!in.hasMoreTokens()) {
  				in=new StringTokenizer(bf.readLine());
  			}
  			return in.nextToken();
  		}
  		int in() throws IOException {
  			return Integer.parseInt(ins());
  		}
  		long inl() throws IOException {
  			return Long.parseLong(ins());
  		}
  		double ind() throws IOException {
  			return Double.parseDouble(ins());
  		}
  	}
  	class Out{
  		PrintWriter out;
  		private OutputStream os;
  		private void init() {
  			out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(os)));
  		}
  		public Out(File file) throws IOException {
  			os=new FileOutputStream(file);
  			init();
  		}
  		public Out(OutputStream os) throws IOException
  		{
  			this.os=os;
  			init();
  		}
  	}
  	class graph{
  		int[]to,nxt,head;
  		int cnt;
  		void init(int n) {
  			cnt=1;
  			for(int i=1;i<=n;i++)
  			{
  				head[i]=0;
  			}
  		}
  		public graph(int n,int m) {
  			to=new int[m+1];
  			nxt=new int[m+1];
  			head=new int[n+1];
  			cnt=1;
  		}
  		void add(int u,int v) {
  			to[cnt]=v;
  			nxt[cnt]=head[u];
  			head[u]=cnt++;
  		}
  	}
   
  	abstract class ioTask{
  		In in;
  		PrintWriter out;
  		public ioTask setIO(File in,File out) throws IOException{
  			this.in=new In(in);
  			this.out=new Out(out).out;
  			return this;
  		}
  		public ioTask setIO(File in,OutputStream out) throws IOException{
  			this.in=new In(in);
  			this.out=new Out(out).out;
  			return this;
  		}
  		public ioTask setIO(InputStream in,OutputStream out) throws IOException{
  			this.in=new In(in);
  			this.out=new Out(out).out;
  			return this;
  		}
  		public ioTask setIO(InputStream in,File out) throws IOException{
  			this.in=new In(in);
  			this.out=new Out(out).out;
  			return this;
  		}
  		void run()throws IOException{
  			 
  		}
  	}
  }