human
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...
Using python3 can you solve the prior task?
 Can you provide a Python program to find the x-th lexicographically smallest of them?
assistant
#Here is Python program to find the x-th lexicographically smallest of them.

import sys
from random import randint
input = lambda : sys.stdin.readline().strip()
intput = lambda : map(int, input().split())

def toStr(new, res):
    a = []
    n = len(new)
    c = 0
    for i in range(n):
        if new[i] == 'a':
            a.append('a')
        else:
            a.append('b' * res[c])
            c += 1
    # print(a)
    return "".join(a)

def solve(k,x,s):
    s += "$"
    stk = 0
    new = []
    for i, ch in enumerate(s):
        if ch == '*': stk += 1
        else:
            if i != 0 and s[i-1] != 'a':
                new.append(stk)
                stk = 0
        if ch == 'a':
            new.append('a')
    q = [y for y in new if y != 'a']
    if not q: return s[:-1]
    n = len(q)
    for i in range(n):
        q[i] = q[i] * k + 1
    for i in range(n-2, -1, -1):
        q[i] *= q[i+1]
    x -= 1

    for i in range(n-1, -1, -1):
        if q[i] > x: break

    res = [0] * n
    if i == n-1:
        res[i] = x
        return toStr(new, res)

    while i < n-1:
        b = x // q[i+1]
        x %= q[i+1]
        res[i] = b
        i += 1
    res[-1] = x
    # print(new, res)
    return toStr(new, res)

def random():
    b = []
    for i in range(randint(0,50)):
        a = randint(0,1)
        x = randint(0,20)
        if a == 0:
            b.append(x * '*')
        else:
            b.append(x * 'a')
    return ''.join(b)

def test(x, k, s):
    A = set()
    def dfs(i, curr):
        if i >= len(s):
            A.add(str(curr))
            return
        if s[i] == '*':
            for j in range(k+1):
                q = curr + 'b'*j
                dfs(i+1, q)
        else: dfs(i+1, curr + 'a')
    dfs(0, "")
    return sorted(A)[x-1]

if __name__ == '__main__':
    # print( test(319, 3, '**a***aa*aa*') )
    # print( test(20, 3, '**a***'))

    T, = intput()
    for _ in range(T):
        n, k, x = intput()
        s = input()
        print( solve(k,x,s) )
        # s = random()
        # k = randint(0,10)
        # x = (randint(0,20))
        #...