{"raw_statement":[{"iden":"problem statement","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, 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.\nSolve $T$ test cases for each input file."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $2 \\leq N \\leq 10^9$\n*   $1 \\leq M \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"2\n3 3\n5 1"},{"iden":"sample output 1","content":"4\n1\n\nFor the first test case, suppose the following $3$ teams participate in the tournament:  \nTeam $T$: players $T_1,T_2,T_3$  \nTeam $W$: players $W_1,W_2,W_3$  \nTeam $R$: players $R_1,R_2,R_3$  \nand suppose the following results occur:\n\n*   Match between Team $T$ and Team $W$\n    *   Game between $T_1$ and $W_1$: $W_1$ wins\n    *   Game between $T_2$ and $W_2$: $W_2$ wins\n    *   Game between $T_3$ and $W_3$: $T_3$ wins\n\n*   Match between Team $T$ and Team $R$\n    *   Game between $T_1$ and $R_3$: $T_1$ wins\n    *   Game between $T_2$ and $R_1$: $R_1$ wins\n    *   Game between $T_3$ and $R_2$: $T_3$ wins\n\n*   Match between Team $W$ and Team $R$\n    *   Game between $W_1$ and $R_3$: $R_3$ wins\n    *   Game between $W_2$ and $R_2$: $R_2$ wins\n    *   Game between $W_3$ and $R_1$: $W_3$ wins\n\nThen, only player $T_3$ from Team $T$ is awarded the perfect record prize.  \nIn this case, the maximum possible number of players who can be awarded the perfect record prize is $4$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}