Given an integer N and list of D hexadecimal digits, what is the smallest positive integer X, whose representation in base 16 consists only of given digits, such that X is divisible by N?

입력 형식

The first line of the input file starts with the integer T, the number of test cases (1 ≤ T ≤ 100). Each test case consists of two lines, in the following format:</p>

N D
d1 d2 . . . dD

N(1 ≤ N ≤ 200, 000) and D(1 ≤ D ≤ 16) are as described in the problem statement (both given here in base 10) and d_i(1 ≤ i ≤ D) are heximal digits allowed to be used in the result. You can assume that digits are sorted.

출력 형식

For each test case, output the smallest positive number X in base 16 such that X is divisible by N and it contains only digits provided. If there is no such number, output ”no solution” instead.

예제 입력

4
1 3
a b c
2 8
1 3 5 7 9 b d f
1207 3
1 a f
33910 4
0 c e f

예제 출력

a
no solution
1aa1aa
c0ffee