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

• 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^9)~.

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