AT_arc203_a [ARC203A] All Winners

$ 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.

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 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.

### Sample Explanation 1 For the first test case, suppose the following $ 3 $ teams participate in the tournament: Team $ T $ : players $ T_1,T_2,T_3 $ Team $ W $ : players $ W_1,W_2,W_3 $ Team $ R $ : players $ R_1,R_2,R_3 $ and suppose the following results occur: - Match between Team $ T $ and Team $ W $ - Game between $ T_1 $ and $ W_1 $ : $ W_1 $ wins - Game between $ T_2 $ and $ W_2 $ : $ W_2 $ wins - Game between $ T_3 $ and $ W_3 $ : $ T_3 $ wins - Match between Team $ T $ and Team $ R $ - Game between $ T_1 $ and $ R_3 $ : $ T_1 $ wins - Game between $ T_2 $ and $ R_1 $ : $ R_1 $ wins - Game between $ T_3 $ and $ R_2 $ : $ T_3 $ wins - Match between Team $ W $ and Team $ R $ - Game between $ W_1 $ and $ R_3 $ : $ R_3 $ wins - Game between $ W_2 $ and $ R_2 $ : $ R_2 $ wins - Game between $ W_3 $ and $ R_1 $ : $ W_3 $ wins Then, only player $ T_3 $ from Team $ T $ is awarded the perfect record prize. In this case, the maximum possible number of players who can be awarded the perfect record prize is $ 4 $ . ### 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.