You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

夏天到了，又到了在夜市大快朵颐吃麻辣小龙虾的季节！

摊主在长桌上整齐地摆放了一排共 $n$ 只新鲜的小龙虾，每只小龙虾占据 $1$ 个单位的宽度。而在这些小龙虾的身后，潜伏着一只传说中的“龙虾霸主”。

作为资深吃货，你的目标是吃掉（移除）尽可能多的小龙虾。但是，龙虾霸主正在虎视眈眈。已知龙虾霸主的体宽为 $w$ 个单位。如果在你吃掉小龙虾的过程中，桌面上出现了连续 $w$ 个或更多的空位（即连续 $w$ 只小龙虾被移走），龙虾霸主就能从这个宽敞的缺口中钻出来夹你的手！

为了安全起见，桌子的最左端和最右端都有坚固的铁板挡住，龙虾霸主无法从两头逃脱，它唯一的出路就是你吃出来的空缺。

请问，在保证不被龙虾霸主钻出来的前提下，你最多能吃掉多少只小龙虾？

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试数据的组数。

接下来每组测试数据包含一行，由两个整数 $n$ 和 $w$ 组成 ($1 \leq n \leq 10^{9}$, $1 \leq w \leq 10^{9}$)，分别表示桌上小龙虾的总数和龙虾霸主的体宽。

输出格式

对于每组测试数据，输出一个整数，表示你最多能吃掉的小龙虾数量。

输入输出样例 #1

输入 #1

5
9 3
13 4
15 14
20 1
1000 42

输出 #1

6
10
14
0
977