该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

显德年间，后周世宗柴荣亲征南唐，师次寿州，围城已久，旌旗蔽日，兵马屯扎。

寿州（今安徽寿县）古代就是铁矿资源地，矿产遍布四方，唯因战事紧急，赵匡胤奉命急炼兵器以备突袭。

铁料品质高低不一，需工匠锻炼而成兵器。铁矿中，每块铁料有其天然品质为正整数$x$ 。

炼制兵器时，成品兵器之刚性系数，计算规则如下：

• 将铁块品质 $x$ 除以工匠能力值 $a$，取其整数部分（即商）；
• 将铁块品质 $x$ 除以工匠能力值 $a$ 所余之余数，加于上述所得；
• 商与余数之和，便为该兵器的刚性系数。

简言之，刚性系数为： 铁块品质除以工匠能力值所得的商与余数之和。

赵匡胤欲于每次开采所得之铁矿中，择最佳品质铁料，铸成锋锐兵器。

围城之际，赵匡胤数度遣人临时开采铁矿。每次开采，矿洞内铁矿品质在区间 $[l, r]$ 之内，而寻找到的工匠能力值为 $a$。

请你助赵匡胤，求出区间 $[l, r]$ 内，最大可得之刚性系数。

输入输出格式

输入格式

第一行包含一个整数 $t$，表示数据组数。

接下来 $t$ 行，每行包含三个整数 $l_i, r_i, a_i$，分别表示矿洞中铁矿的最低品质，最高品质与找到的工匠能力值。

输出格式

对于每组数据，输出一行一个整数，表示对应矿洞中和铁匠能锻造的最大刚性系数。

题目样例

样例#01

5
1 4 3
5 8 4
6 10 6
1 1000000000 1000000000
10 12 8

2
4
5
999999999
5

样例说明

以第一组数据为例，工匠能力值为 $3$，铁块品质区间为 $[1, 4]$。逐一计算：

• 品质 $1$：$1 \div 3 = 0$，余 $1$，刚性系数为 $1$；
• 品质 $2$：$2 \div 3 = 0$，余 $2$，刚性系数为 $2$；
• 品质 $3$：$3 \div 3 = 1$，余 $0$，刚性系数为 $1$；
• 品质 $4$：$4 \div 3 = 1$，余 $1$，刚性系数为 $2$。

故最大刚性系数为 $2$。

数据范围

• $1 \leq t \leq 10^4$，
• $1 \leq l_i \leq r_i \leq 10^9$，
• $1 \leq a_i \leq 10^9$。