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 $a_1,a_2,...,a_k$, can you find a positive integer $y$ such that $y$ is the multiple of $x$ and in decimal representation $y$ contains all digits of $a_1,a_2,...,a_k$.
The first line contains an integer $T (1 \le T \le 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≤1e^8) and $k (1≤k≤10)$, $k integer $a_1,a_2,..,a_k (0≤a_i≤9$ for $i=1..k$ and $a_i \ne a_j$ for $i \ne 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 $1e^{18}$. Every answer that satisfy the conditions descripted above will be accepted.
3 5 3 1 5 7 21 4 2 5 6 9 10 8 0 1 2 3 4 5 6 7 9\n · · · · \n · · · · · \n · · · · · · · · · · \n
175 2592576 976543210\n \n \n
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≤1e^8$
$1≤k≤10$
$0≤a_i≤9,for i=1..k$
$a_i\ne a_j for i\ne j$
your answer $y$ should satisfy $y ≤ 1e^{18}$