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 trên của thầy giáo.

Input

Trong bài này, ta giả định ~(N \le 10^6)~.

• Dòng 1: chứa số nguyên ~N~ là số lượng các cặp ~[a, b]~ cần đếm ~(0 \le N \le 10^6)~.

• ~N~ dòng tiếp theo: mỗi dòng chứa một cặp số nguyên ~a~ và ~b~ ~(1 \le a \le b \le 10^6)~. Các số được ghi cách nhau bởi một dấu cách.

Output

Gồm một dòng ghi số nguyên là tổng ~N~ lần đếm trên.

Scoring

Sample Input 1

2
4 6
4 7

Sample Output 1

5

Notes

Đoạn ~[4, 6]~ có ~2~ số và ~[4, 7]~ có ~3~ số thỏa mãn yêu cầu.

Tổng số là: ~2 + 3 = 5~.