Problem Description

Given a string $S$ contains only $A$ and $B$.

Calculate the Kth string $T$ which doesn't appear in $S$.

Compare the string in order of length,if length is same,then sort in order of lexicographical order.

Input

First line contains a single integer $cases (cases \leq 5)$ which denotes the number of test cases.

For each test case, the first line is string $S (1 \leq |S| \leq 20000)$, the second line have $T+1$ numbers,the first number is $T$,next $T$ number(s) is Kth. $(1 \leq T \leq 10, 1 \leq K \leq 10^9)$

Output

For each case, output $T$ lines.

2
A
1 1
AAABBA
1 1

B
ABA