Câu 3 (2,5 điểm). Trò chơi đếm số

Trong buổi sinh hoạt ngoại khóa, thầy giáo tổ chức một trò chơi nhỏ như sau: mỗi lần thầy viết lên bảng cặp số \(a\) và \(b\), thì các bạn nhanh chóng đếm xem có bao nhiêu số nguyên trong đoạn từ \(a\) đến \(b\) có số lượng các ước của nó là một số nguyên tố.

Ví dụ, với \(a=4\) và \(b=6\), đoạn \([4, 6]\) ta có:

• Số \(4\) có \(3\) ước \((1, 2, 4)\): \(3\) là số nguyên tố;
• Số \(5\) có \(2\) ước \((1, 5)\): \(2\) là số nguyên tố;
• Số \(6\) có \(4\) ước \((1, 2, 3, 6)\): \(4\) không phải là số nguyên tố.

Nên trong đoạn \([4, 6]\) ta đếm được \(2\) số có số lượng ước của nó là số nguyên tố (\(4\) và \(5\)).

Sau \(N\) lần đưa ra các cặp số \(a\) và \(b\), thầy giáo yêu cầu đưa ra kết quả cuối cùng chính là tổng số của \(N\) lần đếm trên.

Yêu cầu: Là một học sinh đam mê lập trình trong lớp, em hãy viết một chương trình để tự động thực hiện yêu cầu của thầy giáo.

Input

Dữ liệu vào: Cho tệp văn bản CAU3.INP có cấu trúc như sau:

• Dòng 1: chứa số nguyên \(N\) là số lượng các cặp \([a, b]\) cần đếm (\(0 \leq N \leq 10^5\));
• \(N\) dòng tiếp theo: mỗi dòng chứa một cặp số nguyên \(a\) và \(b\) (\(1 \leq a \leq b \leq 10^6\)).

Các số được ghi cách nhau bởi một dấu cách.

Output

Kết quả: Ghi ra tệp văn bản CAU3.OUT gồm một dòng ghi số nguyên là tổng \(N\) lần đếm trên.

Example

2
4 6
4 7

5

Scoring

Ràng buộc:

• Có \(40\%\) số test tương ứng \(40\%\) số điểm của bài với \(1 \leq a \leq b \leq 200\) và \(N \leq 200\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 2000\) và \(N \leq 1000\);
• Có \(30\%\) số test tương ứng \(30\%\) số điểm của bài với \(1 \leq a \leq b \leq 10^6\) và \(N \leq 10^5\).