Led On by a Cow to Visit Zenkou Temple— Neo-traditionalism of Japan

This is the hard version of the problem. The difference between the versions is that in this version, $1\le n\le 10$. You can hack only if you solved all versions of this problem.

You are given a non-negative integer $a$ and a non-empty, strictly increasing sequence of digits $d$ of length $n$, where $0 \le d_i \le 9$.

Find the minimum value of $|a - b|$ over all non-negative integers $b$ whose decimal representation contains only digits from $d$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $a$ and $n$ ($0\le a\le 10^{17}$, $1\le n\le 10$).

The second line contains $n$ integers $d_1,d_2,\ldots,d_n$. It is guaranteed that $0\le d_1 \lt d_2 \lt \ldots \lt d_n\le 9$.

Output

For each test case, output the minimum value of $|a - b|$.

Note

In the first test case, $a=0$, $b=0$, and $|a - b|=0$.

In the second test case, $a=11$, $b=11$, and $|a - b|=0$.

In the third test case, $a=222$, $b=333$, and $|a - b|=111$.

In the fourth test case, $a=3333$, $b=999$, and $|a - b|=2334$.