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.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.InputMismatchException;
  import java.util.List;
  import java.util.Set;
  import java.util.TreeSet;
  import java.util.function.Consumer;
  
  /**
   * Provide prove of correctness before implementation. Implementation can cost a
   * lot of time.
   * Anti test that prove that it's wrong.
   * <p>
   * Do not confuse i j k g indexes, upTo and length. Do extra methods!!! Write
   * more informative names to simulation
   * <p>
   * Will program ever exceed limit?
   * Try all approaches with prove of correctness if task is not obvious.
   * If you are given formula/rule: Try to play with it.
   * Analytic solution/Hardcoded solution/Constructive/Greedy/DP/Math/Brute
   * force/Symmetric data
   * Number theory
   * Game theory (optimal play) that consider local and global strategy.
   */
  public class C {
      boolean TLsolution = false;
  
      private void solveOne() {
  
          int n = nextInt(), k = nextInt();
          long x = nextLong();
          String s = nextString();
          char[] S = s.toCharArray();
          if (TLsolution) {
              ArrayDeque<Character> deque = new ArrayDeque<>();
              Set<String> tree = new TreeSet<>();
              backTrack(0, s, k, deque, str -> tree.add(str));
              int cnt = 1;
              for (String cur : tree) {
                  // if(cnt++ == x) {
                  // System.out.println(cur);
                  // }
                  System.out.println("cnt : " + cnt++ + " " + cur);
              }
              System.out.println();
          } else {
              x--;
              // 0. if x == 0
              if (x == 0) {
                  for (int i = 0; i < n; i++) {
                      if (S[i] == 'a') {
                          System.out.print('a');
                      }
                  }
                  System.out.println();
                  return;
              }
  
              int[] lenSt = new int[n];
              lenSt[0] = S[0] == '*' ? 1 : 0;
              for (int i = 1; i < n; i++) {
                  if (S[i] == '*') {
                      lenSt[i] = lenSt[i - 1] + 1;
                  }
              }
  
              List<Integer> bitsLen = new ArrayList<>();
              if (lenSt[lenSt.length - 1] > 0) {
                  bitsLen.add(k * lenSt[lenSt.length - 1] + 1);
              }
              for (int i = n - 2; i >= 0; i--) {
                  if (lenSt[i] > 0 && lenSt[i + 1] == 0) {
                      bitsLen.add(k * lenSt[i] + 1);
                  }
              }
  
              List<Integer> bits = new ArrayList<>();
              for (int bitLen : bitsLen) {
                  bits.add((int)(x % bitLen));
                  x /= bitLen;
              }
              StringBuilder sb = new StringBuilder();
              int p = 0;
          
              for (int i = n - 1; i >= 0; i--) {
                  if (S[i] == 'a') {
                      sb.append('a');
                  } else {
                      for (int j = 0; j < bits.get(p); j++) {
                          sb.append('b');
                      }
                      p++;
                      i -= lenSt[i] - 1;
                  }
              }
              System.out.println(sb.reverse().toString());
  
          }
      }
  
      void backTrack(int ind, String s, final int k, ArrayDeque<Character> deque, Consumer<String> func) {
          if (ind < s.length()) {
              if (s.charAt(ind) == '*') {
                  for (int i = 0; i <= k; i++) {
                      for (int j = 0; j < i; j++) {
                          deque.addLast('b');
                      }
                      backTrack(ind + 1, s, k, deque, func);
                      for (int j = 0; j < i; j++) {
                          deque.removeLast();
                      }
                  }
              } else {
                  deque.addLast('a');
                  backTrack(ind + 1, s, k, deque, func);
                  deque.removeLast();
              }
          } else {
              StringBuilder sb = new StringBuilder();
              for (char ch : deque) {
                  sb.append(ch);
              }
              func.accept(sb.toString());
          }
      }
  
      private void solve() {
          int t = System.in.readInt();
          for (int tt = 1; tt <= t; tt++) {
              solveOne();
          }
      }
  
      class AssertionRuntimeException extends RuntimeException {
  
          AssertionRuntimeException(Object expected,
                  Object actual, Object... input) {
              super("expected = " + expected + ",\n actual = " + actual + ",\n " + Arrays.deepToString(input));
          }
      }
  
      private int nextInt() {
          return System.in.readInt();
      }
  
      private long nextLong() {
          return System.in.readLong();
      }
  
      private String nextString() {
          return System.in.readString();
      }
  
      private int[] nextIntArr(int n) {
          return System.in.readIntArray(n);
      }
  
      private long[] nextLongArr(int n) {
          return System.in.readLongArray(n);
      }
  
      public static void main(String[] args) {
          new C().run();
      }
  
      static class System {
          private static FastInputStream in;
          private static FastPrintStream out;
      }
  
      private void run() {
          System.in = new FastInputStream(java.lang.System.in);
          System.out = new FastPrintStream(java.lang.System.out);
          solve();
          System.out.flush();
      }
  
      private static class FastPrintStream {
          private static final int BUF_SIZE = 8192;
          private final byte[] buf = new byte[BUF_SIZE];
          private final OutputStream out;
          private int ptr = 0;
  
          private FastPrintStream() {
              this(java.lang.System.out);
          }
  
          public FastPrintStream(OutputStream os) {
              this.out = os;
          }
  
          public FastPrintStream(String path) {
              try {
                  this.out = new FileOutputStream(path);
              } catch (FileNotFoundException e) {
                  throw new RuntimeException("FastWriter");
              }
          }
  
          public FastPrintStream print(byte b) {
              buf[ptr++] = b;
              if (ptr == BUF_SIZE)
                  innerflush();
              return this;
          }
  
          public FastPrintStream print(char c) {
              return print((byte) c);
          }
  
          public FastPrintStream print(char[] s) {
              for (char c : s) {
                  buf[ptr++] = (byte) c;
                  if (ptr == BUF_SIZE)
                      innerflush();
              }
              return this;
          }
  
          public FastPrintStream print(String s) {
              s.chars().forEach(c -> {
                  buf[ptr++] = (byte) c;
                  if (ptr == BUF_SIZE)
                      innerflush();
              });
              return this;
          }
  
          // can be optimized
          public FastPrintStream print0(char[] s) {
              if (ptr + s.length < BUF_SIZE) {
                  for (char c : s) {
                      buf[ptr++] = (byte) c;
                  }
              } else {
                  for (char c : s) {
                      buf[ptr++] = (byte) c;
                      if (ptr == BUF_SIZE)
                          innerflush();
                  }
              }
              return this;
          }
  
          // can be optimized
          public FastPrintStream print0(String s) {
              if (ptr + s.length() < BUF_SIZE) {
                  for (int i = 0; i < s.length(); i++) {
                      buf[ptr++] = (byte) s.charAt(i);
                  }
              } else {
                  for (int i = 0; i < s.length(); i++) {
                      buf[ptr++] = (byte) s.charAt(i);
                      if (ptr == BUF_SIZE)
                          innerflush();
                  }
              }
              return this;
          }
  
          private static int countDigits(int l) {
              if (l >= 1000000000)
                  return 10;
              if (l >= 100000000)
                  return 9;
              if (l >= 10000000)
                  return 8;
              if (l >= 1000000)
                  return 7;
              if (l >= 100000)
                  return 6;
              if (l >= 10000)
                  return 5;
              if (l >= 1000)
                  return 4;
              if (l >= 100)
                  return 3;
              if (l >= 10)
                  return 2;
              return 1;
          }
  
          public FastPrintStream print(int x) {
              if (x == Integer.MIN_VALUE) {
                  return print((long) x);
              }
              if (ptr + 12 >= BUF_SIZE)
                  innerflush();
              if (x < 0) {
                  print((byte) '-');
                  x = -x;
              }
              int d = countDigits(x);
              for (int i = ptr + d - 1; i >= ptr; i--) {
                  buf[i] = (byte) ('0' + x % 10);
                  x /= 10;
              }
              ptr += d;
              return this;
          }
  
          private static int countDigits(long l) {
              if (l >= 1000000000000000000L)
                  return 19;
              if (l >= 100000000000000000L)
                  return 18;
              if (l >= 10000000000000000L)
                  return 17;
              if (l >= 1000000000000000L)
                  return 16;
              if (l >= 100000000000000L)
                  return 15;
              if (l >= 10000000000000L)
                  return 14;
              if (l >= 1000000000000L)
                  return 13;
              if (l >= 100000000000L)
                  return 12;
              if (l >= 10000000000L)
                  return 11;
              if (l >= 1000000000L)
                  return 10;
              if (l >= 100000000L)
                  return 9;
              if (l >= 10000000L)
                  return 8;
              if (l >= 1000000L)
                  return 7;
              if (l >= 100000L)
                  return 6;
              if (l >= 10000L)
                  return 5;
              if (l >= 1000L)
                  return 4;
              if (l >= 100L)
                  return 3;
              if (l >= 10L)
                  return 2;
              return 1;
          }
  
          public FastPrintStream print(long x) {
              if (x == Long.MIN_VALUE) {
                  return print("" + x);
              }
              if (ptr + 21 >= BUF_SIZE)
                  innerflush();
              if (x < 0) {
                  print((byte) '-');
                  x = -x;
              }
              int d = countDigits(x);
              for (int i = ptr + d - 1; i >= ptr; i--) {
                  buf[i] = (byte) ('0' + x % 10);
                  x /= 10;
              }
              ptr += d;
              return this;
          }
  
          public FastPrintStream print(double x, int precision) {
              if (x < 0) {
                  print('-');
                  x = -x;
              }
              x += Math.pow(10, -precision) / 2;
              // if(x < 0){ x = 0; }
              print((long) x).print(".");
              x -= (long) x;
              for (int i = 0; i < precision; i++) {
                  x *= 10;
                  print((char) ('0' + (int) x));
                  x -= (int) x;
              }
              return this;
          }
  
          public FastPrintStream println(char c) {
              return print(c).println();
          }
  
          public FastPrintStream println(int x) {
              return print(x).println();
          }
  
          public FastPrintStream println(long x) {
              return print(x).println();
          }
  
          public FastPrintStream println(String x) {
              return print(x).println();
          }
  
          public FastPrintStream println(double x, int precision) {
              return print(x, precision).println();
          }
  
          public FastPrintStream println() {
              return print((byte) '\n');
          }
  
          private void innerflush() {
              try {
                  out.write(buf, 0, ptr);
                  ptr = 0;
              } catch (IOException e) {
                  throw new RuntimeException("innerflush");
              }
          }
  
          public void flush() {
              innerflush();
              try {
                  out.flush();
              } catch (IOException e) {
                  throw new RuntimeException("flush");
              }
          }
      }
  
      private static class FastInputStream {
          private boolean finished = false;
  
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private SpaceCharFilter filter;
  
          public FastInputStream(InputStream stream) {
              this.stream = stream;
          }
  
          public double[] readDoubleArray(int size) {
              double[] array = new double[size];
              for (int i = 0; i < size; i++) {
                  array[i] = readDouble();
              }
              return array;
          }
  
          public String[] readStringArray(int size) {
              String[] array = new String[size];
              for (int i = 0; i < size; i++) {
                  array[i] = readString();
              }
              return array;
          }
  
          public char[] readCharArray(int size) {
              char[] array = new char[size];
              for (int i = 0; i < size; i++) {
                  array[i] = readCharacter();
              }
              return array;
          }
  
          public void readIntArrays(int[]... arrays) {
              for (int i = 0; i < arrays[0].length; i++) {
                  for (int j = 0; j < arrays.length; j++) {
                      arrays[j][i] = readInt();
                  }
              }
          }
  
          public void readLongArrays(long[]... arrays) {
              for (int i = 0; i < arrays[0].length; i++) {
                  for (int j = 0; j < arrays.length; j++) {
                      arrays[j][i] = readLong();
                  }
              }
          }
  
          public void readDoubleArrays(double[]... arrays) {
              for (int i = 0; i < arrays[0].length; i++) {
                  for (int j = 0; j < arrays.length; j++) {
                      arrays[j][i] = readDouble();
                  }
              }
          }
  
          public char[][] readTable(int rowCount, int columnCount) {
              char[][] table = new char[rowCount][];
              for (int i = 0; i < rowCount; i++) {
                  table[i] = this.readCharArray(columnCount);
              }
              return table;
          }
  
          public int[][] readIntTable(int rowCount, int columnCount) {
              int[][] table = new int[rowCount][];
              for (int i = 0; i < rowCount; i++) {
                  table[i] = readIntArray(columnCount);
              }
              return table;
          }
  
          public double[][] readDoubleTable(int rowCount, int columnCount) {
              double[][] table = new double[rowCount][];
              for (int i = 0; i < rowCount; i++) {
                  table[i] = this.readDoubleArray(columnCount);
              }
              return table;
          }
  
          public long[][] readLongTable(int rowCount, int columnCount) {
              long[][] table = new long[rowCount][];
              for (int i = 0; i < rowCount; i++) {
                  table[i] = readLongArray(columnCount);
              }
              return table;
          }
  
          public String[][] readStringTable(int rowCount, int columnCount) {
              String[][] table = new String[rowCount][];
              for (int i = 0; i < rowCount; i++) {
                  table[i] = this.readStringArray(columnCount);
              }
              return table;
          }
  
          public String readText() {
              StringBuilder result = new StringBuilder();
              while (true) {
                  int character = read();
                  if (character == '\r') {
                      continue;
                  }
                  if (character == -1) {
                      break;
                  }
                  result.append((char) character);
              }
              return result.toString();
          }
  
          public void readStringArrays(String[]... arrays) {
              for (int i = 0; i < arrays[0].length; i++) {
                  for (int j = 0; j < arrays.length; j++) {
                      arrays[j][i] = readString();
                  }
              }
          }
  
          public long[] readLongArray(int size) {
              long[] array = new long[size];
              for (int i = 0; i < size; i++) {
                  array[i] = readLong();
              }
              return array;
          }
  
          public int[] readIntArray(int size) {
              int[] array = new int[size];
              for (int i = 0; i < size; i++) {
                  array[i] = readInt();
              }
              return array;
          }
  
          public int read() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar++];
          }
  
          public int peek() {
              if (numChars == -1) {
                  return -1;
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      return -1;
                  }
                  if (numChars <= 0) {
                      return -1;
                  }
              }
              return buf[curChar];
          }
  
          public int peekNonWhitespace() {
              while (isWhitespace(peek())) {
                  read();
              }
              return peek();
          }
  
          public int readInt() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public long readLong() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              } while (!isSpaceChar(c));
              return res * sgn;
          }
  
          public String readString() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              StringBuilder res = new StringBuilder();
              do {
                  if (Character.isValidCodePoint(c)) {
                      res.appendCodePoint(c);
                  }
                  c = read();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          public boolean isSpaceChar(int c) {
              if (filter != null) {
                  return filter.isSpaceChar(c);
              }
              return isWhitespace(c);
          }
  
          public static boolean isWhitespace(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          private String readLine0() {
              StringBuilder buf = new StringBuilder();
              int c = read();
              while (c != '\n' && c != -1) {
                  if (c != '\r') {
                      buf.appendCodePoint(c);
                  }
                  c = read();
              }
              return buf.toString();
          }
  
          public String readLine() {
              String s = readLine0();
              while (s.trim().length() == 0) {
                  s = readLine0();
              }
              return s;
          }
  
          public String readLine(boolean ignoreEmptyLines) {
              if (ignoreEmptyLines) {
                  return readLine();
              } else {
                  return readLine0();
              }
          }
  
          public char readCharacter() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              return (char) c;
          }
  
          public double readDouble() {
              int c = read();
              while (isSpaceChar(c)) {
                  c = read();
              }
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              double res = 0;
              while (!isSpaceChar(c) && c != '.') {
                  if (c == 'e' || c == 'E') {
                      return res * Math.pow(10, readInt());
                  }
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              if (c == '.') {
                  c = read();
                  double m = 1;
                  while (!isSpaceChar(c)) {
                      if (c == 'e' || c == 'E') {
                          return res * Math.pow(10, readInt());
                      }
                      if (c < '0' || c > '9') {
                          throw new InputMismatchException();
                      }
                      m /= 10;
                      res += (c - '0') * m;
                      c = read();
                  }
              }
              return res * sgn;
          }
  
          public boolean isExhausted() {
              int value;
              while (isSpaceChar(value = peek()) && value != -1) {
                  read();
              }
              return value == -1;
          }
  
          public String next() {
              return readString();
          }
  
          public SpaceCharFilter getFilter() {
              return filter;
          }
  
          public void setFilter(SpaceCharFilter filter) {
              this.filter = filter;
          }
  
          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
          }
      }
  
  }