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

Cirno and Number (Hard Version)

Examples