beecrowd | 2820

Bruna's Digits

By Giovanna Kobus Conrado, Universidade de São Paulo BR Brazil

Timelimit: 3

Bruna is learning to count. She already knows d digits. Her brother, Carlos, told her that she can't even form n distinct numbers using those digits only. Bruna, to prove that he is wrong, will write the n smallest numbers that she can make using only the digits she knows in a sheet of paper, but she doesn't know when to stop. Can you help her wit that task?

Input

The first line of input consists of a number (t=100) , the number of test cases.

Each case starts with an integer d (2<=d<=9): the number of digits Bruna has already learned.

The following line will contain d integers vi (1<=vi<=9): the digits Bruna knows.

The last line of each case will be the number (1<=n<=1018).

Output

For each case, print the nth smallest number that can be made using the digits Bruna knows.

Input Sample Output Sample

2

2

1 3

4

3

9 7 8

5

13

78