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.
2
55 982 31372
a*a*aa*aa*a*aa*aa*aaa*aaaaa*a*aa*aaaaa*aaaaa*aa*a*a*a*a
63 9 10946
*aaaaa*aa*a*a*aa*aaaa*a*aa*a*a*aaaa*aaaaa*a*a*aaa*aa*aaa*a*a*aa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabbbbbbbbbabbbbabbbbbaa

#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
 
#define ll long long
#define ld long double
const int mod = 998244353;
const int maxN = 1e6+2;
#define endl '\n'
 
inline void debugMode() {

#ifdef LOCAL
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}

#define int long long

int mul(int a , int b) {
    return (ll)a*b%mod;
}

int my_pow(int a , int p) {
    int ans = 1;
    while(p) {
        if(p&1) {
            ans = mul(a , ans);
        }
        a = mul(a , a);
        p/=2;
    }
    return ans%mod;
}

int inv(int a , int m) {
    return my_pow(a , m-2);
}

int add(int a , int b) {
    int ans= ((ll)a+b)%mod;
    if(ans < 0) {
        ans += mod;
    }
    return ans;
}

int gcd(int a, int b) {
    if(b == 0){
        return a;
    }
    return gcd(b, a%b);
}

void test_case(int tc) {
    int n, k, x;
    cin >> n >> k >> x;
    string s;
    cin >> s;
    // if(tc == 111) {
    //     cout << s << " " << n << " " << k << " " << x;
    // }
    if(n == 1) {
        cout << s << endl;
        return;
    }
    vector<int> b;
    int sz = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'a') {
            if(sz != 0){
                b.push_back(k*sz+1);
            }
            sz = 0;
        }
        else {
            sz++;
        }
    }
    if(sz != 0) {
        b.push_back(k*sz+1);
    }
    if(b.size() == 0) {
        cout << s << endl;
        return;
    }
    debug() << imie(b);
    int p = 1;
    vector<int> prod((int)b.size());
    int j = 0;
    for(int i = (int)b.size()-1; i >= 1; i--) {
        if(p >= (x+b[i]-1)/b[i]) {
            j = i;
            break;
        }
        else {
            p *= b[i];
            prod[i] = p;
        }
    }
    string ans = "";
    int g = -1;
    for(int i = 0 ; i < n; i++) {
        if(s[i] == 'a') {
            ans += "a";
        }
        else{
            g = i;
            break;
        }
    }
    int cnt = -1;
    for(int i = g; i < n; i++) {
        if(cnt >= j) {
            break;
        }
        if(s[i] == '*') {
            cnt++;
            while(i < n && s[i] == '*') {
                i++;
            }
            i--;
        }
        else {
            ans += "a";
        }
    }
    debug() << imie(j) << imie(prod);
    for(int i = j; i < (int)b.size()-1; i++) {
        int k = (x-1+prod[i+1])/prod[i+1];
        for(int j = 0; j < k-1; j++) {
            ans += "b";
        }
        x -= (k-1)*prod[i+1];
        ans += "a";
    }
    for(int i = 0; i < x-1; i++) {
        ans += "b";
    }
    for(int i = n-1; i >= 0; i--) {
        if(s[i] == 'a') {
            ans += "a";
        }
        else {
            break;
        }
    }
    cout << ans << endl;
}

#undef int

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    debugMode();
    int t;
    t = 1;
    cin >> t;
    // while(t--) {
    //     test_case();
    // }
    for(int i = 1 ; i <= t ; i++) {
        // cout << "Case #" << i << ": ";
        test_case(i);
    }
    return 0;
}