多重集是一种允许元素重复的集合。Panda 有一个整数多重集 $S$ 和三个整数 $n, k, m$。最初，$S = \{1, 2, \dots, n\}$。Panda 想要对 $S$ 进行一系列操作。

在每次操作中：从当前的 $S$ 中选择一个整数子集，使得该子集中所有整数的最大公约数（GCD）恰好为 $k$，然后从 $S$ 中移除所有选中的整数。每次操作中必须至少选择一个整数。一个整数集合的最大公约数（GCD）是整除该集合中每个整数的最大正整数 $g$。例如，$\gcd(12, 16) = 4$，$\gcd(6, 9, 12) = 3$，且 $\gcd(6, 10, 15) = 1$。请记住，单个整数的 GCD 就是该整数本身。

在第一次操作之前，Panda 可以选择 $S$ 中至多 $m$ 个整数并修改它们的值。每个被选中的整数可以被修改为 $1$ 到 $n$ 之间的任意值。请注意，此修改允许 $S$ 包含重复的值。

你需要帮助 Panda 求出他能成功执行的最大操作次数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，输入为一行，包含三个整数 $n, k, m$ ($1 \le k \le n \le 10^{18}$，$0 \le m \le n$)，其中 $n$ 是初始多重集的上限，$k$ 是子集要求的 GCD，而 $m$ 是最多可以修改的值的个数。

输出格式

对于每个测试用例，在一行中输出一个整数，表示可以成功执行的最大操作次数。

样例

输入样例 1

2
4 1 0
5 3 1

输出样例 1

2
2

说明

对于第一个测试用例，一种可能的方案包含两次操作：

1. 选择子集 $\{1, 4\}$ 并将其移除。
2. 选择子集 $\{2, 3\}$ 并将其移除。

对于第二个测试用例，一种方案是将 $1$ 修改为 $3$，然后执行两次操作：

1. 选择子集 $\{3\}$ 并将其移除。
2. 选择子集 $\{3\}$ 并将其移除。