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