Problem Statement

$N$ teams are participating in a team shogi tournament. Each team consists of $M$ players. This tournament is a round-robin format, with a total of $\frac{N(N-1)}{2}$ matches played. In each match, the $M$ players from each team are randomly matched against each other, and one player always wins while the other loses. After all matches are played, each player will have played exactly $N-1$ games, and players who won all their games will be awarded the perfect record prize. Find the maximum possible number of players who can be awarded the perfect record prize.

Solve $T$ test cases for each input file.

Constraints

• $1 \leq T \leq 2 \times 10^5$
• $2 \leq N \leq 10^9$
• $1 \leq M \leq 10^9$
• All input values are integers.

Input

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

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

N M

Output

Output the answers in a total of $T$ lines. The $t$-th line should contain the maximum possible number of players who can be awarded the perfect record prize for the $t$-th test case.