Yukikaze and Smooth numbers

Problem Description

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.

Sample Input

5
13 2
75 18
38 8
24 7
62 9

Sample Output

4
54
25
18
34

Source

2020 Multi-University Training Contest 6