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.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{
			 
		}
	}
}