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\)