Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó. Ví dụ: Số 11 là số nguyên tố vì nó chỉ có hai ước là 1 và 11; số 15 không phải là số nguyên tố vì nó có 4 ước gồm: 1, 3, 5, 15; số 1 không phải là số nguyên tố vì nó có 1 ước là 1.

Yêu cầu: Cho số nguyên \(N\) (\(1 \le N \le 10^6\)) và \(N\) đoạn số nguyên \([L_i, R_i]\) (\(1 \le L_i < R_i \le 10^7\); \(1 \le i \le N\)). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn \([L_i, R_i]\).

Dữ liệu vào

Từ tệp tin văn bản snt.inp, gồm:

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i, R_i\) (ngăn cách nhau bởi một khoảng trắng).

Dữ liệu ra

Ghi ra tệp tin văn bản snt.out gồm \(N\) dòng, dòng thứ \(i\) ghi một số nguyên là số lượng số nguyên tố thuộc đoạn \([L_i, R_i]\).

Ví dụ

snt.inp

2
14 16
11 25

snt.out

0
5

Giải thích: Số lượng số nguyên tố thuộc 2 đoạn tương ứng:

• Đoạn \([14, 16]\): không có số nguyên tố;
• Đoạn \([11, 25]\): có 5 số nguyên tố là 11, 13, 17, 19, 23.

Ràng buộc

• Subtask 1 (40% số test tương ứng 40% số điểm của bài): \(1 \le N < 10^3\); \(1 \le L_i < R_i \le 10^3\).
• Subtask 2 (60% số test tương ứng 60% số điểm của bài): \(10^3 \le N \le 10^6\); \(1 \le L_i < R_i \le 10^7\).