Zghh likes number, but he doesn't like writing problem description. So he will just give you a problem instead of telling a long story for it.
Now given a positive integer x and k digits a1,a2,...,ak, can you find a positive integer y such that y is the multiple of x and in decimal representation y contains all digits of a1,a2,...,ak.
输入描述:
The first line contains an integer T (1<=T<=10000) which is the number of test case.The following T lines each line is a test case, start with two integer x (1<=x<=1e8) and k (1<=k<=10), k integer a1,a2,..,ak (0<=ai<=9 for i=1..k and ai!=aj for i!=j) is following.
输出描述:
For each test case output your answer y. Your answer should be a positive integer without leading zero and should be no more than 1e18. Every answer that satisfy the conditions descripted above will be accepted.
示例1
输入
复制
3
5 3 1 5 7
21 4 2 5 6 9
10 9 0 1 2 3 4 5 6 7 9
说明
175 is the multiple of 5 and contains 1,5,7
2592576 is the multiple of 21 and contains 2,5,6,9
976543210 is the multiple of 10 and contains 0,1,2,3,4,5,6,7,9
备注:
Constraint of data
1<=T<=10000
1<=x<=1e8
1<=k<=10
0<=ai<=9,for i=1..k
ai!=aj for i!=j
your answer y should satisfy y <= 1e18