A faulty car odometer always skips some digits when it is increasing. For example when the digit 4 is missing, then it proceeds from digit 3 to digit 5 (assuming that digits 3 and 5 are not missing), always skipping the digit 4, regardless of position.

Knowing that odometer starts always at zero, if the odometer now reads M, how many miles has the car actually traveled?

Input specification

The first line will contain the number of cases ~T \leq 100,000~. Then for each case, there will be two lines: in the first one will appear ~N (0 \leq N \leq 8)~, the number of missing digits in the odometer, and ~M (0 \leq M \leq 10^{18})~; in the second line will appear separated by spaces the N missing digits ~d_1, d_2, ... , d_N (1 \leq di \leq 9)~.

Output specification

For each case print a single line with the number of miles that the car has actually traveled.

Sample input

2
1 2005
3
3 560
4 3 9

Sample output

1462
175