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

奶牛引路，参访善光寺

——日本新传统主义

本题为困难版本。两个版本的区别在于：本版本中 $1\le n\le 10$。仅当您已解决本题所有版本时，才可进行 Hack。

给定一个非负整数 $a$ 和一个长度为 $n$ 的、非空且严格递增的数字序列 $d$（即每位数字满足 $0 \le d_i \le 9$）。

求所有满足以下条件的非负整数 $b$ 中，$|a - b|$ 的最小值：$b$ 的十进制表示中仅包含序列 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $a$ 和 $n$（$0\le a\le 10^{17}$，$1\le n\le 10$）。

第二行包含 $n$ 个整数 $d_1,d_2,\ldots,d_n$。保证 $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|$.

对于每个测试用例，输出 $|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$.

在第一个测试用例中，$a=0$，$b=0$，且 $|a - b|=0$。

在第二个测试用例中，$a=11$，$b=11$，且 $|a - b|=0$。

在第三个测试用例中，$a=222$，$b=333$，且 $|a - b|=111$。

在第四个测试用例中，$a=3333$，$b=999$，且 $|a - b|=2334$。