Hidden Digits
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ digits $$$d_0$$$, $$$d_1$$$, ... $$$d_{n - 1}$$$. Find the minimum positive integer $$$x$$$ such that for all $$$0 \le i < n$$$, the decimal representation of number $$$x + i$$$ contains the digit $$$d_i$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

The second line contains a string of $$$n$$$ digits $$$d_0 d_1 \ldots d_{n-1}$$$ ($$$0 \le d_i \le 9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer $$$x$$$ — the smallest positive integer such that the decimal representation of $$$x+i$$$ contains the digit $$$d_i$$$ for all $$$0 \le i < n$$$.

Example

Input

    6512345501234323999982443531010000000072018446744073709551616

Output

    1
    10
    92
    45296
    701
    10367486