# AB String

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## 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.

## Sample Input

2
A
1 1
AAABBA
1 1

## Sample Output

B
ABA

hujie

## Source

BestCoder Round #54 (div.1) (\$)