All Winners

AtCoder

IDarc203_a

Time2000ms

Memory256MB

Difficulty—

$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$ [samples]

Samples

Input #1

2
3 3
5 1

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

API Response (JSON)

{
  "problem": {
    "name": "All Winners",
    "description": {
      "content": "$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, th",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc203_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$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, th...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments