Problem Statement

Find the minimum possible value of a positive integer $n$ that satisfies the following two conditions:

• $n$ is a multiple of $K$.
• The decimal representation of $n$ contains $S$ as a substring.

$T$ test cases are given, so find the answer for each.

What is a substring? A substring of a string $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$. For example, ab and b are substrings of abc, but ac and cba are not substrings of abc.

Constraints

• $T$ is an integer.
• $1 \leq T \leq 200$
• $K$ is an integer.
• $1 \leq K \leq 10^9$
• $S$ is a string consisting of digits (0 - 9).
• The first character of $S$ is not 0.
• $1 \leq |S| \leq 5 \times 10^5$
• For each input file, the sum of $|S|$ over all test cases is at most $5 \times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

$\textrm{case}_i$ represents the $i$-th test case. Each test case is given in the following format:

K
S

Output

Output $T$ lines. The $i$-th line ($1 \leq i \leq T$) should contain the answer to the $i$-th test case.