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: /**
   * Created by Himanshu
   **/
  
  import java.util.*;
  import java.io.*;
  import java.math.*;
  
  public class C1620 {
      public static void main(String[] args) throws IOException {
          PrintWriter out = new PrintWriter(System.out);
          Reader s = new Reader();
          int t = s.i();
          while (t-- > 0) {
              int n = s.i(), k = s.i();
              long x = s.l();
              char[] arr = s.s().toCharArray();
              StringBuilder sb = new StringBuilder();
              int idx = -1;
              ArrayList<Integer> list = new ArrayList<>();
              for (int i=0;i<n;i++) {
                  if (arr[i] == 'a') {
                      sb.append('a');
                      idx++;
                      list.add(0);
                  } else {
                      if (i == 0 || arr[i-1] != arr[i]) {
                          sb.append('*');
                          idx++;
                          list.add(k);
                      } else {
                          list.set(idx, list.get(idx)+k);
                      }
                  }
              }
              arr = sb.toString().toCharArray();
              n = arr.length;
              long [] dp = new long[n+1];
              dp[n] = 1L;
              for (int i=n-1;i>=0;i--) {
                  if (arr[i] == 'a') {
                      dp[i] = dp[i+1];
                  } else {
                      dp[i] = (list.get(i)+1)*dp[i+1];
                  }
                  if (dp[i] < 0) {
                      dp[i] = Long.MAX_VALUE;
                  }
                  if (dp[i] >= x) {
                      break;
                  }
              }
              sb = new StringBuilder();
              for (int i=0;i<n-1;i++) {
                  if (arr[i] == 'a') sb.append('a');
                  else {
                      if (dp[i] >= x) {
                          long a = (x-1)/dp[i+1];
                          x -= (a*dp[i+1]);
                          while (a > 0) {
                              sb.append('b');
                              a--;
                          }
                      }
                  }
              }
              if (arr[n-1] == 'a') sb.append('a');
              else {
                  while (x > 1) {
                      sb.append('b');
                      x--;
                  }
              }
              out.println(sb);
  
  
  
  
  
  
  
  
  
  
  
  
  
  //            long[] dp = new long[n + 1];
  //            if (arr[n - 1] == 'a') dp[n - 1] = 1L;
  //            else dp[n - 1] = k + 1;
  //            long[] prev = new long[n + 1];
  //            prev[n - 1] = prev[n] = 1L;
  //            for (int i = n - 2; i >= 0; i--) {
  //                if (arr[i] == 'a') {
  //                    dp[i] = dp[i + 1];
  //                    prev[i] = dp[i];
  //                } else {
  //                    dp[i] = dp[i + 1] + prev[i + 1] * k;
  //                    prev[i] = prev[i + 1];
  //                }
  //                if (dp[i] < 0) dp[i] = Long.MAX_VALUE;
  //                if (dp[i] >= x) {
  //                    break;
  //                }
  //            }
  //            StringBuilder sb = new StringBuilder();
  //            for (int i = 0; i < n - 1; i++) {
  //                if (arr[i] == 'a') sb.append('a');
  //                else {
  //                    if (dp[i] >= x) {
  //                        long temp = x - dp[i + 1];
  //                        long a = temp / prev[i + 1];
  //                        if (temp % prev[i] != 0) a++;
  //                        long val = (a - 1) * prev[i + 1] + dp[i + 1];
  //                        while (a > 0) {
  //                            sb.append('b');
  //                            a--;
  //                        }
  //                        x -= val;
  //                    }
  //                }
  //            }
  //            if (arr[n - 1] == 'a') {
  //                sb.append('a');
  //            }
  //
  //            if (arr[n - 1] == '*' && x > 0) {
  //                while (x > 1) {
  //                    sb.append('b');
  //                    x--;
  //                }
  //            }
  //            out.println(sb);
          }
          out.flush();
      }
  
      public static void shuffle(long[] arr) {
          int n = arr.length;
          Random rand = new Random();
          for (int i = 0; i < n; i++) {
              long temp = arr[i];
              int randomPos = i + rand.nextInt(n - i);
              arr[i] = arr[randomPos];
              arr[randomPos] = temp;
          }
      }
  
      private static long phi(long n) {
          long result = n;
          for (long i = 2; i * i <= n; i++) {
              if (n % i == 0) {
                  while (n % i == 0)
                      n /= i;
                  result -= result / i;
              }
          }
          if (n > 1)
              result -= result / n;
          return result;
      }
  
      private static int gcd(int a, int b) {
          if (b == 0) return a;
          return gcd(b, a % b);
      }
  
      public static long nCr(long[] fact, long[] inv, int n, int r, long mod) {
          if (n < r)
              return 0;
          return ((fact[n] * inv[n - r]) % mod * inv[r]) % mod;
      }
  
      private static void factorials(long[] fact, long[] inv, long mod, int n) {
          fact[0] = 1;
          inv[0] = 1;
          for (int i = 1; i <= n; ++i) {
              fact[i] = (fact[i - 1] * i) % mod;
              inv[i] = power(fact[i], mod - 2, mod);
          }
      }
  
      private static long power(long a, long n, long p) {
          long result = 1;
          while (n > 0) {
              if (n % 2 == 0) {
                  a = (a * a) % p;
                  n /= 2;
              } else {
                  result = (result * a) % p;
                  n--;
              }
          }
          return result;
      }
  
      private static long power(long a, long n) {
          long result = 1;
          while (n > 0) {
              if (n % 2 == 0) {
                  a = (a * a);
                  n /= 2;
              } else {
                  result = (result * a);
                  n--;
              }
          }
          return result;
      }
  
      private static long query(long[] tree, int in, int start, int end, int l, int r) {
          if (start >= l && r >= end) return tree[in];
          if (end < l || start > r) return 0;
          int mid = (start + end) / 2;
          long x = query(tree, 2 * in, start, mid, l, r);
          long y = query(tree, 2 * in + 1, mid + 1, end, l, r);
          return x + y;
      }
  
      private static void update(int[] arr, long[] tree, int in, int start, int end, int idx, int val) {
          if (start == end) {
              tree[in] = val;
              arr[idx] = val;
              return;
          }
          int mid = (start + end) / 2;
          if (idx > mid) update(arr, tree, 2 * in + 1, mid + 1, end, idx, val);
          else update(arr, tree, 2 * in, start, mid, idx, val);
          tree[in] = tree[2 * in] + tree[2 * in + 1];
      }
  
      private static void build(int[] arr, long[] tree, int in, int start, int end) {
          if (start == end) {
              tree[in] = arr[start];
              return;
          }
          int mid = (start + end) / 2;
          build(arr, tree, 2 * in, start, mid);
          build(arr, tree, 2 * in + 1, mid + 1, end);
          tree[in] = (tree[2 * in + 1] + tree[2 * in]);
      }
  
      static class Reader {
          private InputStream mIs;
          private byte[] buf = new byte[1024];
          private int curChar, numChars;
  
          public Reader() {
              this(System.in);
          }
  
          public Reader(InputStream is) {
              mIs = is;
          }
  
          public int read() {
              if (numChars == -1) throw new InputMismatchException();
              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = mIs.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }
                  if (numChars <= 0) return -1;
              }
              return buf[curChar++];
          }
  
          public String nextLine() {
              int c = read();
              while (isSpaceChar(c)) c = read();
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = read();
              } while (!isEndOfLine(c));
              return res.toString();
          }
  
          public String s() {
              int c = read();
              while (isSpaceChar(c)) c = read();
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = read();
              } while (!isSpaceChar(c));
              return res.toString();
          }
  
          public long l() {
              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 int i() {
              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 double d() throws IOException {
              return Double.parseDouble(s());
          }
  
          public boolean isSpaceChar(int c) {
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }
  
          public boolean isEndOfLine(int c) {
              return c == '\n' || c == '\r' || c == -1;
          }
  
          public int[] arr(int n) {
              int[] ret = new int[n];
              for (int i = 0; i < n; i++) {
                  ret[i] = i();
              }
              return ret;
          }
  
          public long[] arrLong(int n) {
              long[] ret = new long[n];
              for (int i = 0; i < n; i++) {
                  ret[i] = l();
              }
              return ret;
          }
      }
  //    static class pairLong implements Comparator<pairLong> {
  //        long first, second;
  //
  //        pairLong() {
  //        }
  //
  //        pairLong(long first, long second) {
  //            this.first = first;
  //            this.second = second;
  //        }
  //
  //        @Override
  //        public int compare(pairLong p1, pairLong p2) {
  //            if (p1.first == p2.first) {
  //                if(p1.second > p2.second) return 1;
  //                else return -1;
  //            }
  //            if(p1.first > p2.first) return 1;
  //            else return -1;
  //        }
  //    }
  //    static class pair implements Comparator<pair> {
  //        int first, second;
  //
  //        pair() {
  //        }
  //
  //        pair(int first, int second) {
  //            this.first = first;
  //            this.second = second;
  //        }
  //
  //        @Override
  //        public int compare(pair p1, pair p2) {
  //            if (p1.first == p2.first) return p1.second - p2.second;
  //            return p1.first - p2.first;
  //        }
  //    }
  }
  
  