시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB1641099066.667%

## 문제

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 ≤ x ≤ N and for every prime divisor p of x, p ≤ 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?

## 입력

The first line contains an integer Q (1 ≤ Q ≤ 5 × 104) 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 ≤ N, K ≤ 105).

## 출력

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

## 예제 입력 1

4
10 3
10 4
15 3
5 20


## 예제 출력 1

6
6
7
4


## 출처

• 문제를 만든 사람: Juan Pablo Marín Rosas