AT_arc203_a [ARC203A] All Winners

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

入力は以下の形式で標準入力から与えられる。 > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ M $

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

### Sample Explanation 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 $ です。 ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 2 \leq N \leq 10^9 $ - $ 1 \leq M \leq 10^9 $ - 入力される値は全て整数