CF2228C2 Cirno and Number (Hard Version)

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 $ .

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 $ .