You are given an integer $N$ that is represented in the form of string $S$ of length $M$. You can remove at most 1 digit from the number after removing the rest of the digits that are arranged in the same order.

Example

For $N = 2134$, if you delete the digit $3$, the new number is $214$.

You are also given an integer $K$. Find the maximum possible value of ($N$ mod $K$) after deleting at most 1 digit from number $N$.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains two space-separated integers $M$ and $K$.
• The second line of each test case contains string $S$.

Output format

For each test case, print the maximum possible value of the mod function in a new line.

Constraints

$1 \le T \le 10 \\ 1 \le N \le 10^{10^5} \\ 1 \le K \le 10^9$