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: // 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();
  
    static String solve(String s, int k, long x) {
      //  a  (*  *)  a  a  (*  *  *)  a  *
      //     ^             ^             ^
      //     2k+1          3k+1          k+1
      //
      int n = s.length();
      StringBuilder sb = new StringBuilder();
      int e = n - 1;
      char[] ca = s.toCharArray();
      long y = x - 1;
      while (e >= 0) {
        if (ca[e] == 'a') {
          sb.append('a');
          e--;
        } else {
          int b = e - 1;
          while (b >= 0 && ca[b] == '*') {
            b--;
          }
          int len = e - b;
          // number of choices at this spot
          int m = len * k + 1;
          int numb = (int) (y % m);
          for (int i = 0; i < numb; i++) {
            sb.append('b');
          }
          y /= m;
          e = b;
        }
        // System.out.format("  %s e:%2d %s\n", s, e, sb.toString());
      }
      return sb.reverse().toString();
    }
  
    // Wrong answer on test 4
    // It is NOT
    static String solveA(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!)
      // The last entry is the special [n,n,1]
      List<long[]> chunks = detectChunks(s, k);
      // System.out.format("  chunks: %s\n", Utils.traceListLongArray(chunks));
  
      StringBuilder sb = new StringBuilder();
      long y = x - 1;
      int m = chunks.size();
      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 - 1) {
          break;
        }
        long[] next = chunks.get(i + 1);
        // If next count is not overflow
        if (next[2] > 0) {
          int q = (int) (y / next[2]);
          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();
    }
  
    // 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 test(String s, int k, long 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);
      }
    }
  
    static void doTest() {
      /*
      {
        String s = "*a*a****a*****a******a****a***a*****a******a******a*aa*a*a*a*a*aa**";
        int k = 1999;
        long x = (long) 1e18;
        String ans = solve(s, k, x);
        System.out.format("  %s %d %d\n  -> %s\n", s, k, x, ans);
      }
      {
        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("  %s %d %11d\n  -> %s\n", s, k, x, ans, 100);
      }
      */
      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);
        }
        test(s, k, x);
      }
      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);
      }
    }
  }
  