给定一个包含 $n$ 个数字的序列 $d_0, d_1, \dots, d_{n-1}$。请找到最小的正整数 $x$，使得对于所有 $0 \le i < n$，数字 $x + i$ 的十进制表示中都包含数字 $d_i$。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。 第二行包含一个长度为 $n$ 的数字字符串 $d_0d_1 \dots d_{n-1}$ ($0 \le d_i \le 9$)。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数 $x$，即满足对于所有 $0 \le i < n$，数字 $x + i$ 的十进制表示中都包含数字 $d_i$ 的最小正整数。

样例

输入 1

6
5
12345
5
01234
3
239
9
998244353
10
1000000007
20
18446744073709551616

输出 1

1
10
92
45296
701
10367486