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 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 ≤ N ≤ 2.10^5~) và N đoạn số nguyên (~1 ≤ L_i ≤ R_i ≤ 10^7~). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn

Dữ liệu vào:

• 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(ngăn cách nhau bởi một khoảng trắng)

Dữ liệu ra:

-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 .

Ví dụ:

Input

2
14 16
11 25

Output

0
5

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm của bài với ~1 \le N \le 10^3; 1 \le L \le R \le 10^3~
• Có 60% số test tương ứng 60% số điểm của bài với ~10^3 < N \le 2.10^5; 1 \le L \le R \le 10^7~.