Lịch sử của số nguyên tố gắn liền với bình minh của nền văn minh nhân loại. Những dấu vết đầu tiên được tìm thấy trên tấm xương Ishango có từ hơn ~20.000~ năm trước, nhưng phải đến thời kỳ Hy Lạp cổ đại, lý thuyết về số nguyên tố mới thực sự được hệ thống hóa. Khoảng năm ~300~ TCN, Euclid đã ghi danh vào lịch sử với bộ sách Cơ sở khi chứng minh rằng số lượng số nguyên tố là vô hạn và đặt nền móng cho Định lý cơ bản của Số học.

Đến thế kỷ III TCN, Eratosthenes xứ Cyrene - nhà toán học, thiên văn học kiêm thủ thư vĩ đại của Thư viện Alexandria - đã phát minh ra thuật toán "Sàng" nổi tiếng. Ý tưởng của ông xuất phát từ hình ảnh một chiếc sàng cơ học dùng để lọc ngũ cốc: viết tất cả các số lên một tấm bảng sáp hoặc giấy da, sau đó chọc thủng lỗ tại vị trí các hợp số, để lại một bề mặt chỉ còn chứa những "viên ngọc" số nguyên tố. Trải qua hàng thiên kỷ, từ các nghiên cứu của Fermat, Euler, Gauss cho đến ứng dụng mã hóa RSA hiện đại, số nguyên tố vẫn luôn giữ vị trí trái tim của lý thuyết số.

Trong bài tập này, bạn được cấp một khoảng giá trị ~[L, R]~ cùng ~Q~ truy vấn. Mỗi truy vấn yêu cầu tính tổng các số nguyên tố nằm trong đoạn ~[A_i, B_i]~.

Input

• Dòng ~1~: Chứa hai số nguyên ~L~ và ~R~.
• Dòng ~2~: Chứa số nguyên ~Q~ - số lượng truy vấn.
• ~Q~ dòng tiếp theo: Mỗi dòng chứa hai số nguyên ~A_i~ và ~B_i~ - khoảng cần tính tổng của truy vấn thứ ~i~.
• Lưu ý: ~1 \le L \le R \le 10^9~, ~R - L \le 10^5~, ~Q \le 10^5~, ~L \le A_i \le B_i \le R~.

Output

• In ra ~Q~ dòng, mỗi dòng chứa một số nguyên duy nhất: Tổng các số nguyên tố nằm trong đoạn ~[A_i, B_i]~ tương ứng.

Example Input

1 10
2
1 5
6 10

Example Output

10
7