Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Fuy học lớp 12 toán 1 và cậu rất yêu thích các con số nguyên tố. Fuy muốn đưa ra một thử thách như sau:

Cho ba số nguyên dương ~l, r, val~. Với mỗi số nguyên dương ~x~, ta quy định ~f(x)~ như sau:

• ~f(x) = |val - x|~ nếu ~x~ là số nguyên tố;
• ~f(x) = 0~ nếu ~x~ không phải số nguyên tố.

Hãy tính tổng mọi ~f(x)~ với ~l \le x \le r~.

Bạn phải trả lời ~q~ truy vấn như vậy.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l, r, val~ ~(l \le r \le 10^5,\ val \le 10^9)~.

Kết quả

• In ra ~q~ dòng, dòng thứ ~i~ chứa kết quả của truy vấn thứ ~i~.

Giới hạn

• ~1 \le q \le 10^5~; ~1 \le l \le r \le 10^5~; ~1 \le val \le 10^9~.
• Subtask 1 (20% số test): ~q, l, r \le 100~.
• Subtask 2 (30% số test): ~q, l, r \le 10^4~.
• Subtask 3 (30% số test): Trong mỗi truy vấn: ~val \le l~ hoặc ~val \ge r~.
• Subtask 4 (20% số test): Không có ràng buộc gì thêm.

Sample Input 1

1
4 10 6

Sample Output 1

2

Giải thích

~|6 - 5| + |6 - 7| = 2~.