Yukikaze is learning number theory. In number theory, a $k$-smooth number is an integer whose prime factors are all less or equal to $k$ . Given $n$ and $k$, she wants to know how many $k$-smooth numbers are less or equal to $n$.
Input
The input contains several test cases, and the first line contains a single integer $T(1≤T≤50)$, the number of test cases. Each of the next T lines contains two integers $n(1 \leq n \leq 10^9), k(1 \leq k \leq 10^9)$, denoting the question described above.
Output
For each test case, output the answer in a single line.