eolymp
bolt
Try our new interface for solving problems
Problems

Serial Numbers

Serial Numbers

Time limit 3 seconds
Memory limit 64 MiB

In the factory of ACM Computerized Manufacturing Ltd. (ACM Ltd.), items are manufactured in assembly lines and are given imprinted serial numbers to distinguish them from one another. The serial numbers are generated by a special kind of simplistic multi-function counter machine which generates serial number sequentially in increasing order (1, 2, 3, and so on).

As the counter machine has multiple functions embedded in its simple design, some substrings are reserved as op-codes command which must not be presented in the machine's serial number output. For example if 23 is a command op-code, then 23 must not be presented in the substring of a serial number - assuming there is no other command op-code, the number sequence would go like this: 1, 2, 3, ..., 21, 22, 24, 25, ..., 121, 122, 124, 125, ..., 228, 229, 240, 241, 242, ....

This result in serial number that is different from the actual production batch number recorded in the system. The system does not map the relationship between both numbers and/or record exact serial numbers for each item, this may cause problems when an individual item needs to be tracked (e.g. for a recall or inspection). Given the production batch number of an item, your task is to determine the serial number for that item.

Input data

The first line of input contains an integer T (T100) denoting the number of testcases. Each testcase begins with an integer K (1K10) the number of op-codes in the counter machine, followed by K integers (1 to 10 digits, with leading zeroes preserved) representing each op-codes.

The second line contains an integer N (1N100) the number of requested production batch number, followed by N integers representing each production batch number.

Output data

For each testcase, print N integers the serial numbers of corresponding production batch number. Two adjacent integers are separated by a single space. You may assume that these numbers are fit in signed 32-bit integer.

Examples

Input example #1
4
1 4
2 3 5
1 2	
3 4 5 6
2 4 13
3 4 13 888
3 012 345 6789
2 12345 67890
Output example #1
3 6
5 6 7
5 16 1230
12391 68273