問題文

数列 $A=(1,2,\dots ,N)$ があります。あなたは、以下の一連の操作を、$A$ の要素数が $2$ 以上である間繰り返します。

• $A$ の要素を $1$ つ選ぶ。これを $x$ とする。
• $x$ 以外の $A$ の要素を $1$ つ選ぶ。これを $y$ とする。
• コスト $(x+y)modM$ を支払って、$y$ を $A$ から削除する。

あなたは、支払うコストの合計を最小化したいと思っています。

$T$ 個のテストケースが与えられるので、それぞれについてコストの最小値を求めてください。

入力

入力の $1$ 行目に、テストケースの数 $T$ が以下の形式で与えられる。

$T$

そして、$T$ 個のテストケースが続く。これらはそれぞれ以下の形式で与えられる。

$N$ $M$

• 入力はすべて整数
• $1\le T\le {10}^5$
• $2\le N\le {10}^9$
• $1\le M\le 2N$

出力

$T$ 行出力してください。

$i(1\le i\le T)$ 行目には、$i$ 番目のテストケースについて、コストの合計の最小値を出力してください。

最後に改行してください。

サンプル

1
3 2

1