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.FileInputStream;
  import java.io.FileWriter;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.io.PrintWriter;
  import java.util.ArrayList;
  import java.util.Collections;
  import java.util.InputMismatchException;
  import java.util.List;
  
  public class Main {
  
      static class Data {
          char type;
          int count;
  
          public Data(char type, int count) {
              this.type = type;
              this.count = count;
          }
      }
  
      public static void main(String[] args) throws Exception {
          int tc = io.nextInt();
          for (int i = 0; i < tc; i++) {
              solve();
          }
          io.close();
      }
  
      private static void solve() throws Exception {
          List<Data> queue = new ArrayList<>();
          int n = io.nextInt();
          long k = io.nextInt();
          long x = io.nextLong() - 1;
          String s = io.next();
          for (char c : s.toCharArray()) {
              if (queue.isEmpty() || queue.get(queue.size() - 1).type != c) {
                  queue.add(new Data(c, 0));
              }
              queue.get(queue.size() - 1).count++;
          }
          StringBuilder sb = new StringBuilder();
          for (int i = queue.size() - 1; i >= 0; i--) {
              if (queue.get(i).type == '*') {
                  long c = queue.get(i).count * k + 1;
                  for (int j = 0; j < x % c; j++) {
                      sb.append('b');
                  }
                  x /= c;
              } else {
                  for (int j = 0; j < queue.get(i).count; j++) {
                      sb.append('a');
                  }
              }
          }
          io.println(sb.reverse().toString());
      }
  
      static void sort(int[] a) {
          ArrayList<Integer> l = new ArrayList<>(a.length);
          for (int i : a) {
              l.add(i);
          }
          Collections.sort(l);
          for (int i = 0; i < a.length; i++) {
              a[i] = l.get(i);
          }
      }
  
      //-----------PrintWriter for faster output---------------------------------
      public static FastIO io = new FastIO();
  
      //-----------MyScanner class for faster input----------
      static class FastIO extends PrintWriter {
          private InputStream stream;
          private byte[] buf = new byte[1 << 16];
          private int curChar, numChars;
  
          // standard input
          public FastIO() {
              this(System.in, System.out);
          }
  
          public FastIO(InputStream i, OutputStream o) {
              super(o);
              stream = i;
          }
  
          // file input
          public FastIO(String i, String o) throws IOException {
              super(new FileWriter(o));
              stream = new FileInputStream(i);
          }
  
          // throws InputMismatchException() if previously detected end of file
          private int nextByte() {
              if (numChars == -1) {
                  throw new InputMismatchException();
              }
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars == -1) {
                      return -1; // end of file
                  }
              }
              return buf[curChar++];
          }
  
          // to read in entire lines, replace c <= ' '
          // with a function that checks whether c is a line break
          public String next() {
              int c;
              do {
                  c = nextByte();
              } while (c <= ' ');
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = nextByte();
              } while (c > ' ');
              return res.toString();
          }
  
          public String nextLine() {
              int c;
              do {
                  c = nextByte();
              } while (c < '\n');
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = nextByte();
              } while (c > '\n');
              return res.toString();
          }
  
          public int nextInt() {
              int c;
              do {
                  c = nextByte();
              } while (c <= ' ');
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = nextByte();
              }
              int res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res = 10 * res + c - '0';
                  c = nextByte();
              } while (c > ' ');
              return res * sgn;
          }
  
          public long nextLong() {
              int c;
              do {
                  c = nextByte();
              } while (c <= ' ');
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = nextByte();
              }
              long res = 0;
              do {
                  if (c < '0' || c > '9') {
                      throw new InputMismatchException();
                  }
                  res = 10 * res + c - '0';
                  c = nextByte();
              } while (c > ' ');
              return res * sgn;
          }
  
  
          public double nextDouble() {
              return Double.parseDouble(next());
          }
      }
      //--------------------------------------------------------
  }