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.
def solution(n, k, x, s):
    current_len = 0
    astrics = []
    for c in s:
        if   c == '*':
            current_len += 1
        elif c == 'a':
            if current_len != 0:
                astrics.append(current_len)
            current_len = 0
    if current_len != 0:
        astrics.append(current_len)
    astrics = list(map(lambda y: k*y+1, astrics))
    x -= 1
    result = []
    for num in reversed(astrics):
        m = x % num
        x //= num
        result.append(m)

    answer = ''
    c = s[0]
    if c == 'a':
        answer = 'a'
    for i in range(1, n):
        if s[i] == 'a' and s[i - 1] == '*':
            num = result.pop()
            answer += num * 'b'
        if s[i] == 'a':
            answer += 'a'
    if s[n - 1] == '*':
        num = result.pop()
        answer += num * 'b'


    return answer


if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        n, k, x = list(map(int, input().split()))
        s = input()
        print(solution(n, k, x, s))
