Lại là sàng Eratosthenes

Points: 1

Time limit: 1.0s

Memory limit: 98M

Author:

Problem types

Cho hai số nguyên dương \(L\) ≤ \(R\). Hãy đếm xem trong đoạn \([L, R]\) có bao nhiêu số nguyên tố.

Input:

Dòng đầu ghi số nguyên dương \(T\) là số bộ test. (\(T\) <= \(10^5\))
T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\) cách nhau bởi một dấu cách. \((1 < L \le R \le 10^8)\)

Output:

Với mỗi cặp số \(L\) và \(R\), ghi ra trên một dòng số số nguyên tố trong đoạn \([L, R]\). (Đoạn \([L, R]\) ít hơn \(10^8\) phần tử)

Example:

Input1:

2
2 3
10 15

Output1:

2
2

Input2:

Output2:

1
2
6

Comments