The problem is kept simple. Since this is a Shandong provincial selection simulation contest, no large sample cases are provided; I hope everyone is doing fine.

For a given constant $K$, we define the "Shandong coefficient" of $N$ as the smallest divisor of $KN$ that is greater than $N$. For example, if $K=3$, the Shandong coefficient of $4$ is $6$.

Given a constant $K$ and a limit $LIM$, you need to calculate how many numbers have a Shandong coefficient no greater than $LIM$.

Input

The first line contains an integer $T$, representing the number of test cases. For each test case, the input consists of a single line containing two integers $LIM$ and $K$.

Output

For each test case, output a single integer on a new line representing the answer.

Constraints

• For 20% of the data, $LIM \le 10^4$.
• For 40% of the data, $LIM \le 10^6$.
• For 100% of the data, $LIM \le 10^{12}$, $K \le 60$.
• Since this is not an FJOI simulation, we inform you that $T \le 50$.

Examples

Input 1

5
114 5
1145 14
114514 19
11451419 19
23000000 23

Output 1

53
746
49815
4981675
9842921