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). 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). For each test case, output the minimum value of (|a - b|). 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).