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.

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^5\)).
• \(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

• Ghi ra một dòng duy nhất là số nguyên là tổng của \(N\) lần đếm trên.

Example

2
4 6
4 7

5

Scoring

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