Problem Description

You are given an integer $n$ and a parameter $k$. You need to perform exactly $m$ operations on this number. In each operation, you may choose one of the following two actions:

• Add $1$ to the number, i.e. $n \gets n + 1$.
• Take the number modulo $k$, i.e. $n \gets n \bmod k$.

Find the minimum possible value of $n$ after performing $m$ operations.

Input Format

There are $T$ test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

• A single line contains three positive integers $n, m, k$.

Output Format

For each test case, output a single non-negative integer — the minimum possible value of $n$.

7
1 2 2
3 1 5
2 3 3
6 7 1
1 6 1
4 9 1
9 1 1

0
3
0
0
0
0
0

Hint

Explanation

There are $7$ test cases in the sample.

For the first test case:

• In the first operation, set $n \gets n + 1$, so now $n = 2$.
• In the second operation, set $n \gets n \bmod k$, so now $n = 0$.

For the second test case:

• In the first operation, set $n \gets n \bmod k$, so now $n = 3$.

It can be proven that these operation sequences both make $n$ as small as possible.

Constraints

For $100\%$ of the data:

• $1 \le T \le 2 \times 10^5$;
• $0 \le n, m, k < 2^{30}$;
• $k \ge 1$.