Một số nguyên dương được gọi là Số đặc biệt nếu số lượng các ước số của nó là một số nguyên tố.

Ví dụ:

● Số 4 có các ước là {1, 2, 4}. Số lượng ước là 3. Vì 3 là số nguyên tố nên 4 là số đặc biệt.

● Số 6 có các ước là {1, 2, 3, 6}. Số lượng ước là 4. Vì 4 không phải là số nguyên tố nên 6 không phải là số đặc biệt.

Nam được cô giáo giao cho một danh sách các câu hỏi, mỗi câu hỏi yêu cầu đếm xem trong đoạn từ [L, R] có bao nhiêu số đặc biệt. Vì danh sách rất dài nên Nam phải viết một chương trình để giải quyết nhanh chóng.

Yêu cầu: Cho Q câu hỏi, mỗi câu hỏi gồm hai số nguyên L và R. Hãy đếm số lượng số đặc biệt trong đoạn [L, R].

Dữ liệu vào: Đọc từ tệp văn bản SODB.INP gồm:

● Dòng đầu tiên chứa số nguyên Q (1 ≤ Q ≤ 10^5) là số lượng câu hỏi.

● Q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương L và R (1 ≤ L ≤ R ≤ 10^6).

Dữ liệu ra: Ghi ra tệp văn bản SODB.OUT gồm Q dòng, mỗi dòng là đáp án cho câu hỏi tương ứng.

Ví dụ:

Input:

2

1 5

7 10

Output:

4

2

Giải thích: Từ 1 đến 5 có 4 số đặc biệt là: 2, 3, 4, 5. Từ 7 đến 10 có 2 số đặc biệt là: 7, 9.

Ràng buộc:

● 30% số điểm tương ứng với Q ≤ 100 và R ≤ 1000.

● 40% số điểm tương ứng với Q ≤ 10^5 và R ≤ 10^5.

● 30% số điểm tương ứng với Q ≤ 10^5 và R ≤ 10^6.