题解

题面描述

$Gerry$ 的店里有 $n$ 个顾客使用兑换券兑换 $m$ 个糖果，每张糖果兑换券可以兑换 $k$ 个糖果。但实际上，单次兑换中所需要的兑换券数 $y$ 与获得的糖果数 $x$ 满足下列类似于四舍五入的关系：

题目内容

$Gerry$的店里有$n$个顾客使用兑换券兑换$m$个糖果，每张糖果兑换券可以兑换$k$个糖果。单次兑换所需的兑换券数$y$与糖果数$x$有如下关系，类似于四舍五入。

$mod$表示取模运算

$Gerry$有如下要求

• 每个客户最多交易$1$次
• $m$个糖果需要全部兑换完

$Gerry$想知道要兑换完所有的糖果，至少需要多少张兑换券，请帮忙计算一下。

输入描述

第一行一个数字$T(1≤T≤1000)$

接下来$T$行，每行三个数字:

$n,m,k;(1≤n≤10^9,$$1≤m≤10^{18},2 ≤k≤10^9)$

对于每组数据输入$n、m、k$分别表示顾客数量、糖果数量和每张兑换券兑换多少糖果。

输出描述

输出$T$行，每行表示最少需要多少兑换券。

样例1

输入

2
3 300 100
2 100 160

输出

3
0