Berland 扑克游戏是用一副 $$$n$$$ 牌进行的,其中 $$$m$$$ 是小丑牌。 $$$k$$$ 玩家玩这个游戏($$$n$$$ 可以被 $$$k$$$ 整除)。
游戏开始时,每位玩家从牌堆中拿走 $$$\frac{n}{k}$$$ 卡(因此每张牌都由一名玩家拿走)。拥有最大王牌数量的玩家为获胜者,他获得的分数等于 $$$x - y$$$,其中 $$$x$$$ 是获胜者手上王牌的数量,而 $$$y$$$ 是所有其他玩家中王牌数量最多的。如果有两个或两个以上的玩家拥有最大数量的小丑,则所有玩家都是获胜者,并获得 $$$0$$$ 积分。
以下是一些示例:
- $$$n = 8$$$,$$$m = 3$$$,$$$k = 2$$$。如果一名玩家获得 $$$3$$$ 百搭牌和 $$$1$$$ 普通牌,另一名玩家获得 $$$0$$$ 百搭牌和 $$$4$$$ 普通牌,则第一位玩家为获胜者,获得 $$$3 - 0 = 3$$$ 分;
- $$$n = 4$$$,$$$m = 2$$$,$$$k = 4$$$。两名玩家获得普通牌,另外两名玩家获得小丑牌,因此他们都是赢家并获得 $$$0$$$ 积分;
- $$$n = 9$$$,$$$m = 6$$$,$$$k = 3$$$。如果第一个玩家拿到$$$3$$$百搭牌,第二个玩家拿到$$$1$$$百搭牌和$$$2$$$普通牌,第三个玩家拿到$$$2$$$百搭牌和$$$1$$$普通牌,那么第一位玩家就是赢家,他得到$$$3 - 2 = 1$$$点;
- $$$n = 42$$$,$$$m = 0$$$,$$$k = 7$$$。由于没有小丑,每个人都会获得 $$$0$$$ 小丑,每个人都是赢家,每个人都会获得 $$$0$$$ 积分。
给定 $$$n$$$、$$$m$$$ 和 $$$k$$$,计算玩家赢得比赛可以获得的最大分数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。
然后是测试用例。每个测试用例包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$($$$2 \le n \le 50$$$、$$$0 \le m \le n$$$、$$$2 \le k \le n$$$、$$$k$$$ 是 $$$n$$$ 的约数)。
输出
对于每个测试用例,打印一个整数 - 玩家赢得比赛可以获得的最大分数。
示例
输入 #1
4 8 3 2 4 2 4 9 6 3 42 0 7
输出 #1
3 0 1 0
注意
声明中描述了示例的测试用例。