L - Looking for the Risk Factor

Time limit: 3 seconds
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

For testing a new cryptographic algorithm, engineers working for a large investment bank need to compute a value they named the Risk Factor of the algorithm. Informally, the Risk Factor is the amount of numbers less than or equal to a certain value $N$, that aren’t multiples of prime numbers greater than a certain value $K$.

More formally, given the values $N$ and $K$, the Risk Factor is the number of elements of the following set:

{$x$ such that $2 \leq x \leq N$ and for every prime divisor $p$ of $x$, $p \leq K$}

The engineers need to compute the Risk Factor for different values of $N$ and $K$ and have prepared a set of queries for you to answer. Can you help them?

Input

The first line contains an integer $Q$ $(1 \leq Q \leq 5 \times 10^4)$ representing the number of queries that the engineers prepared for you. Each of the following $Q$ lines describes a query with two integers $N$ and $K$ $(2 \leq N, K \leq 10^5)$.

Output

Output $Q$ lines, each line with an integer indicating the Risk Factor for the corresponding query of the input.

Sample test(s)

Input
4 10 3 10 4 15 3 5 20
Output
6 6 7 4