G. GCD of Subsets
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A multiset is a type of collection that allows duplicate elements. Panda has an integer multiset $$$S$$$ and three integers $$$n,k,m$$$. Initially, $$$S = \{1, 2, \ldots, n\}$$$. Panda wants to perform a series of operations on $$$S$$$. In each operation: choose a subset of integers from the current $$$S$$$ such that the greatest common divisor (GCD) of all integers in this chosen subset is exactly $$$k$$$, and then remove all the selected integers from $$$S$$$.

At least one integer must be selected in each operation. The greatest common divisor (GCD) of a set of integers is the largest positive integer $$$g$$$ that divides every integer in the set. For example, $$$\gcd(12,16)=4$$$, $$$\gcd(6,9,12)=3$$$, and $$$\gcd(6,10,15)=1$$$. Remember that the GCD of a single integer is the integer itself.

Before the first operation, Panda may choose at most $$$m$$$ integers in $$$S$$$ and change their values. Each selected integer can be changed to any value between $$$1$$$ and $$$n$$$. Note that this modification allows $$$S$$$ to contain duplicate values.

You should help panda find the maximum number of operations he can successfully perform.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), denoting the number of test cases.

For each test case, the input is one line with three integers $$$n, k, m$$$ ($$$1 \le k \le n \le 10^{18}$$$, $$$0 \le m \le n$$$), where $$$n$$$ is the upper limit of the initial multiset, $$$k$$$ is the required GCD for subsets, and $$$m$$$ is the maximum number of values that can be changed.

Output

For each test case, print an integer in one line, denoting the maximum number of operations that can be successfully performed.

Example
Input
2
4 1 0
5 3 1
Output
2
2
Note

For the first test case, a possible solution involves two operations:

  1. Choose subset $$$\{1, 4\}$$$ and remove them.
  2. Choose subset $$$\{2, 3\}$$$ and remove them.

For the second test case, a solution is to change $$$1$$$ into $$$3$$$, then perform two operations:

  1. Choose subset $$$\{3\}$$$ and remove it.
  2. Choose subset $$$\{3\}$$$ and remove it.