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 c1620;

import java.io.File;
import java.lang.invoke.MethodHandles;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;

//
// Educational Codeforces Round 119 (Rated for Div. 2) 2021-12-18 07:35
// C. BA-String
// https://codeforces.com/contest/1620/problem/C
// time limit per test 2 seconds; memory limit per test 256 megabytes
// public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
//
// 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 .
//
// Two strings a and b are different if they either have different lengths or there exists such a
// position i that a_i \neq 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 \ne 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 "" is only counted once, even though there are two ways to replace asterisks
// with characters 'b' to get it.
//
public class C1620C {
  static final int MOD = (int)1e9+7;
  static final Random RAND = new Random();

  // Runtime error on test 4
  static String solve(String s, int k, long x) {
    //  a  (*  *)  a  a  (*  *  *)  a  *
    //     ^             ^             ^
    //     2k+1          3k+1          k+1
    //
    // List of [b,e) and count (which could be 0 to indicate overflow!)
    List<long[]> chunks = detectChunks(s, k);

    // System.out.println(Arrays.toString(cts));
    StringBuilder sb = new StringBuilder();
    long y = x - 1;
    int m = chunks.size() - 1;
    for (int i = 0; i <= m; i++) {
      int b = (int) (i == 0 ? 0 : chunks.get(i-1)[1]);
      long[] curr = chunks.get(i);
      for (int j = b; j < curr[0]; j++) {
        sb.append('a');
      }
      if (i == m) {
        break;
      }
      long[] next = chunks.get(i + 1);
      int q = next[2] <= 0 ? 0 : (int) (y / next[2]);
      if (q < 0) {
        throw new RuntimeException("Unexpected nagative q!");
      }
      y -= next[2] * q;
      for (int j = 0; j < q; j++) {
        sb.append('b');
      }
      // System.out.format("  i:%d m:%d chunk: %s sb:%s\n", i, m, Arrays.toString(chunk), sb.toString());
    }
    return sb.toString();
  }

  static final long MAX_VALUE = (long) 1e18 + 1;

  // Detects List of [b,e) and suffix count
  static List<long[]> detectChunks(String s, int k) {

    int n = s.length();
    char[] ca = s.toCharArray();
    // List of [b,e) and count
    List<long[]> chunks = new ArrayList<>();
    int b = 0;
    while (b < n) {
      if (ca[b] == 'a') {
        b++;
      } else {
        int e = b + 1;
        while (e < n && ca[e] == '*') {
          e++;
        }
        chunks.add(new long[] {b, e, 0});
        b = e;
      }
    }
    chunks.add(new long[] {n, n, 1L});
    int m = chunks.size();
    for (int i = m - 2; i >= 0; i--) {
      long[] curr = chunks.get(i);
      long[] next = chunks.get(i + 1);
      // Note that although x (in [1,10^18] does not exceed the total number of different BA-strings
      // The total number itself could overflow long however! We use value 0 to indicate overflow.
      curr[2] = next[2] * ((curr[1] - curr[0]) * k + 1);
      if (curr[2] < 0) {
        curr[2] = 0;
      }
    }
    return chunks;
  }

  static long getTotal(String s, int k) {
    List<long[]> chunks = detectChunks(s, k);
    return chunks.get(0)[2];
  }

  static String solveNaive(String s, int k, long x) {
    List<long[]> chunks = detectChunks(s, k);
    List<String> all = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    dfs(s.length(), chunks, 0, k, sb, all);
    Collections.sort(all);
    for (int i = 0; i < all.size(); i++) {
      // System.out.format("  %6d: %s\n", i + 1, all.get(i));
    }
    return all.get((int) (x - 1));
  }

  static void dfs(int n, List<long[]> chunks, int idx, int k,
      StringBuilder sb, List<String> output) {
    if (idx == chunks.size()) {
      output.add(sb.toString());
      return;
    }
    int len = sb.length();
    long[] chunk = chunks.get(idx);
    for (int i = (int) (idx == 0 ? 0 : chunks.get(idx-1)[1]); i < chunk[0]; i++) {
      sb.append('a');
    }
    int maxNumB = (int) ((chunk[1] - chunk[0]) * k);
    for (int i = 0; i <= maxNumB; i++) {
      dfs(n, chunks, idx + 1, k, sb, output);
      sb.append('b');
    }
    sb.setLength(len);
  }

  static void doTest() {
    {
      int n = 85;
      int k = 343;
      long x = 815444752179661601L;
      String s = "*a*aaaa*a*aaaaaaa*aaa*a*a*a***a***a*a*aa***a**a*a*a***a***aaaa*aaaa***aa**aaaaa*a***a";
      String ans = solve(s, k, x);
      System.out.format("  %30s %d %11d -> %s\n", s, k, x, ans);
    }
    for (int t = 0; t < 20; t++) {
      int n = 1 + RAND.nextInt(30);
      int k = RAND.nextInt(10);
      char[] ca = new char[n];
      for (int i = 0; i < n; i++) {
        ca[i] = RAND.nextInt(3) == 0 ? 'a' : '*';
      }
      String s = new String(ca);
      long total = getTotal(s, k);
      // Note that nextLong() does ((long)next(32) << 32) + next(32); and could be negative!
      long x = 1 + ThreadLocalRandom.current().nextLong(total);
      if (x <= 0) {
        System.out.format("total:%d x:%d\n", total, x);
      }
      String ans = solve(s, k, x);
      System.out.format("  %30s %d %11d -> ", s, k, x);
      if (x < 10000000) {
        String exp = solveNaive(s, k, x);
        System.out.format("%s%s\n", ans, ans.equals(exp) ? "":" Expected " + exp);
      } else {
        System.out.format("%s ?\n", ans);
      }
    }
    System.exit(0);
  }

  public static void main(String[] args) {
    // doTest();
    Scanner in = getInputScanner();
    int T = in.nextInt();
    for (int t = 1; t <= T; t++) {
      int n = in.nextInt();
      int k = in.nextInt();
      // !!! x MUST be read as nextLong !!!
      long x = in.nextLong();
      String s = in.next();
      String ans = solve(s, k, x);
      System.out.println(ans);
    }
    in.close();
  }

  static Scanner getInputScanner() {
    try {
      final String USERDIR = System.getProperty("user.dir");
      final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
      final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
      return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
    } catch (Exception e) {
      return new Scanner(System.in);
    }
  }
}
