問題一覧 > 通常問題

No.1803 Remainder of Sum

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 50
作問者 : NatsubiSogan / テスター : nok0 penguinman noko_ut
お気に入りにしたユーザー ProblemId : 7514 / 自分の提出
問題文最終更新日: 2021-12-21 12:52:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 326 (順位表) の他の問題:

Problem Statement

There is a sequence $A=(1,2,\dots,N)$. While the number of elements of $A$ is at least $2$, you repeat the following series of operations.

  • Choose $1$ element of $A$. Call it $x$.
  • Choose $1$ element of $A$ other than $x$. Call it $y$.
  • Pay a cost of $(x+y) \bmod M$ and delete $y$ from $A$.

You want to minimize the total cost paid.

You are given $T$ test cases. For each of them, find the minimum cost.

Input

The $1$st line of the input gives the number of test cases $T$ in the following format. 

$T$

Then, $T$ test cases follow. Each of them is given in the following format. 

$N$ $M$
  • All input values are integers.
  • $1 \leq T \leq 10^5$
  • $2 \leq N \leq 10^9$
  • $1 \leq M \leq 2N$

Output

Output $T$ lines.

On the $i \ (1 \leq i \leq T)$-th line, output the minimum total cost for the $i$-th test case.

Print a newline at the end.

Sample

Sample 1
Input
1
3 2
Output
1

Initially, $A=(1,2,3)$. A total cost of $1$ can be achieved as follows.

  • Let $x=1,\ y=3$. Pay a cost of $(1+3) \bmod 2 = 0$ and delete $y \ (=3)$ from $A$. Now $A=(1,2)$.
  • Let $x=1,\ y=2$. Pay a cost of $(1+2) \bmod 2 = 1$ and delete $y \ (=2)$ from $A$. Now $A=(1)$, and the operations end.

No sequence of operations makes the cost $0$, so the answer is $1$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。