#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunknown-pragmas"
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
constexpr long long SZ = 1e5 + 7;
constexpr long long inf = 1e18;
constexpr long long mod = 1e9 + 7;
constexpr long long MOD = 998244353;
constexpr long double PI = 3.141592653589793238462;
void __print(long long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << x; }
void __print(const char *x) { cerr << x; }
void __print(const string &x) { cerr << x; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) {
    cerr << (f++ ? ", " : "");
    __print(i);
  }
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) {
    cerr << ", ";
  }
  _print(v...);
}
template <class T>
bool amin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool amax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T1, typename T2>
istream &operator>>(istream &istream, pair<T1, T2> &p) {
  return (istream >> p.first >> p.second);
}
template <typename T>
istream &operator>>(istream &istream, vector<T> &v) {
  for (auto &it : v) {
    cin >> it;
  }
  return istream;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &ostream, const pair<T1, T2> &p) {
  return (ostream << p.first << " " << p.second);
}
template <typename T>
ostream &operator<<(ostream &ostream, const vector<T> &c) {
  for (auto &it : c) {
    cout << it << " ";
  }
  return ostream;
}
long long tc_cnt = 1;
long long modpow(long long a, long long b, long long m = mod) {
  a = a & m;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % m;
    }
    b = b >> 1;
    a = (a * a) % m;
  }
  return ans;
}
long long modinv(long long a, long long m = mod) { return modpow(a, m - 2); }
long long modadd(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a + b) % m) + m) % m;
}
long long modsub(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a - b) % m) + m) % m;
}
long long modmul(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a * b) % m) + m) % m;
}
long long moddiv(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (modmul(a, modinv(b, m), m) + m) % m;
}
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
const long long dx[8] = {0, 1, -1, 0, -1, -1, 1, 1};
const long long dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
long long mul(long long a, long long b) {
  long long ans = 0;
  while (b) {
    if (b & 1) {
      ans += a;
    }
    b = b >> 1;
    a += a;
    if (a > inf) {
      a = inf;
    }
    if (ans > inf) {
      ans = inf;
    }
  }
  return ans;
}
void oreo() {
  long long n, k, x;
  cin >> n >> k >> x;
  x--;
  string s;
  cin >> s;
  vector<long long> cnt;
  long long c = 0;
  for (long long i = 0; i < n; ++i) {
    if (s[i] == 'a') {
      cnt.push_back(c);
      c = 0;
    } else {
      c++;
    }
  }
  cnt.push_back(c);
  ;
  vector<long long> m((long long)cnt.size());
  m[(long long)m.size() - 1] = 1;
  for (long long i = (long long)cnt.size() - 2; i >= 0; --i) {
    m[i] = mul(m[i + 1], k * cnt[i + 1] + 1);
  };
  vector<long long> ans((long long)cnt.size());
  for (long long i = 0; i < (long long)cnt.size(); ++i) {
    ans[i] = x / m[i];
    x %= m[i];
  };
  for (long long i = 0; i < (long long)cnt.size(); ++i) {
    for (long long j = 0; j < ans[i]; ++j) {
      cout << 'b';
    }
    if (i + 1 != (long long)cnt.size()) {
      cout << 'a';
    }
  }
  cout << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  cin >> t;
  while (t--) oreo();
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wunused-variable"
#pragma GCC diagnostic ignored "-Wunknown-pragmas"
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
constexpr long long SZ = 1e5 + 7;
constexpr long long inf = 1e18;
constexpr long long mod = 1e9 + 7;
constexpr long long MOD = 998244353;
constexpr long double PI = 3.141592653589793238462;
void __print(long long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << x; }
void __print(const char *x) { cerr << x; }
void __print(const string &x) { cerr << x; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) {
    cerr << (f++ ? ", " : "");
    __print(i);
  }
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) {
    cerr << ", ";
  }
  _print(v...);
}
template <class T>
bool amin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool amax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T1, typename T2>
istream &operator>>(istream &istream, pair<T1, T2> &p) {
  return (istream >> p.first >> p.second);
}
template <typename T>
istream &operator>>(istream &istream, vector<T> &v) {
  for (auto &it : v) {
    cin >> it;
  }
  return istream;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &ostream, const pair<T1, T2> &p) {
  return (ostream << p.first << " " << p.second);
}
template <typename T>
ostream &operator<<(ostream &ostream, const vector<T> &c) {
  for (auto &it : c) {
    cout << it << " ";
  }
  return ostream;
}
long long tc_cnt = 1;
long long modpow(long long a, long long b, long long m = mod) {
  a = a & m;
  long long ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % m;
    }
    b = b >> 1;
    a = (a * a) % m;
  }
  return ans;
}
long long modinv(long long a, long long m = mod) { return modpow(a, m - 2); }
long long modadd(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a + b) % m) + m) % m;
}
long long modsub(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a - b) % m) + m) % m;
}
long long modmul(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (((a * b) % m) + m) % m;
}
long long moddiv(long long a, long long b, long long m = mod) {
  a = a % m;
  b = b % m;
  return (modmul(a, modinv(b, m), m) + m) % m;
}
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
const long long dx[8] = {0, 1, -1, 0, -1, -1, 1, 1};
const long long dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
long long mul(long long a, long long b) {
  long long ans = 0;
  while (b) {
    if (b & 1) {
      ans += a;
    }
    b = b >> 1;
    a += a;
    if (a > inf) {
      a = inf;
    }
    if (ans > inf) {
      ans = inf;
    }
  }
  return ans;
}
void oreo() {
  long long n, k, x;
  cin >> n >> k >> x;
  x--;
  string s;
  cin >> s;
  vector<long long> cnt;
  long long c = 0;
  for (long long i = 0; i < n; ++i) {
    if (s[i] == 'a') {
      cnt.push_back(c);
      c = 0;
    } else {
      c++;
    }
  }
  cnt.push_back(c);
  ;
  vector<long long> m((long long)cnt.size());
  m[(long long)m.size() - 1] = 1;
  for (long long i = (long long)cnt.size() - 2; i >= 0; --i) {
    m[i] = mul(m[i + 1], k * cnt[i + 1] + 1);
  };
  vector<long long> ans((long long)cnt.size());
  for (long long i = 0; i < (long long)cnt.size(); ++i) {
    ans[i] = x / m[i];
    x %= m[i];
  };
  for (long long i = 0; i < (long long)cnt.size(); ++i) {
    for (long long j = 0; j < ans[i]; ++j) {
      cout << 'b';
    }
    if (i + 1 != (long long)cnt.size()) {
      cout << 'a';
    }
  }
  cout << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  cin >> t;
  while (t--) oreo();
  return 0;
}

```