题目描述

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$ 的约数）。

输出格式

对于每个测试用例，输出一个整数，表示一名玩家获胜时能获得的最大分数。

说明/提示

样例的测试用例已在题目描述中给出。

由 ChatGPT 4.1 翻译

样例

4
8 3 2
4 2 4
9 6 3
42 0 7

3
0
1
0