A - All Winners Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

将棋の団体戦の大会に N チームが参加しています。 各チームは M 人の選手からなります。 この大会は総当たり戦で、合計で \frac{N(N-1)}{2} 試合が行われます。 各試合ではそれぞれのチームの M 人の選手同士がランダムにマッチングされて対局を行い、必ず一方が勝って一方が負けます。 全ての試合が行われた後、各選手はちょうど N-1 回対局を行ったことになりますが、全ての対局に勝った選手には全勝賞が与えられます。 全勝賞を与えられる選手の人数としてありうる最大値を求めてください。

1 つの入力ファイルにつき、T 個のテストケースを解いてください。

制約

  • 1 \leq T \leq 2 \times 10^5
  • 2 \leq N \leq 10^9
  • 1 \leq M \leq 10^9
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
case_1
case_2
\vdots
case_T

各ケースは以下の形式で与えられる。

N M

出力

答えを合計 T 行で出力せよ。 t 行目には、t 番目のテストケースについて全勝賞を与えられる選手の人数としてありうる最大値を出力せよ。

入力例 1

2
3 3
5 1

出力例 1

4
1

1 つ目のテストケースについて、 以下の 3 チームが大会に参加しているとします。
チーム T：選手 T_1,T_2,T_3
チーム W：選手 W_1,W_2,W_3
チーム R：選手 R_1,R_2,R_3
として、以下の結果になったとします。

  • チーム T 対 チーム W の試合
    • T_1 対 W_1 の対局 → W_1 勝ち
    • T_2 対 W_2 の対局 → W_2 勝ち
    • T_3 対 W_3 の対局 → T_3 勝ち
  • チーム T 対 チーム R の試合
    • T_1 対 R_3 の対局 → T_1 勝ち
    • T_2 対 R_1 の対局 → R_1 勝ち
    • T_3 対 R_2 の対局 → T_3 勝ち
  • チーム W 対 チーム R の試合
    • W_1 対 R_3 の対局 → R_3 勝ち
    • W_2 対 R_2 の対局 → R_2 勝ち
    • W_3 対 R_1 の対局 → W_3 勝ち

このとき、全勝賞を与えられるのはチーム T の選手 T_3 のみです。
このケースでは、全勝賞を与えられる選手の人数としてありうる最大値は 4 です。

Score : 400 points

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.

Sample Input 1

2
3 3
5 1

Sample Output 1

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