|
Matcom Online Grader
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
L - Looking for the Risk Factor
Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
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