A positive proper divisor is a positive divisor of a number $n$, excluding $n$ itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.
Peter has two positive integers $n$ and $d$. He would like to know the number of integers below $n$ whose maximum positive proper divisor is $d$.
Input
There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 10^6)$, indicating the number of test cases. For each test case:
The first line contains two integers $n$ and $d$ $(2 \le n, d \le 10^9)$.
Output
For each test case, output an integer denoting the answer.
