Bài 9: Sprime

Đăng bởi Admin

Tháng 10 9, 2022

https://chuyenhalong.ucode.vn/problems/sprime-119071

An rất yêu thích số nguyên tố, đồng thời cũng rất yêu thích số 5 . Do đó, cậu ta luôn coi các số nguyên tố có tổng các chũ̃ số chia hết cho 5 là số đặc biệt. Lần này, thầy giáo đưa cho An 2 số nguyên dương $L, R(L \leq R)$ . An rất muốn biết trong đoạn $[L, R]$ có bao nhiêu số đặc biệt nên nhờ các bạn trả lời giúp.

Đầu vào
– Dòng đầu tiên chứa số nguyên dương $T \leq 100$ là số lượng test trong file.
– $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $L, R(L \leq R)$ theo thứ tự, phân tách nhau bởi dấu cách.
Đầu ra
– Gồm $T$ dòng, mỗi dòng ghi một số là số lượng số đặc biệt trong đoạn $[L, R]$ , tương ứng theo thứ tự vào. Dòng thứ $i$ là kết quả của cặp số $[L, R]$ ở dòng $i+1$ .

Ràng buộc
– $20 \%$ số test có $T=1 ; L \leq R \leq 20$
– $20 \%$ số test tiếp theo có $T=1 ; L, R \leq 10^3$
– $30 \%$ số test tiếp theo có $2 \leq T \leq 10 ; L, R \leq 10^5$
– $30 \%$ số test cuối cùng có $10 \leq T \leq 100 ; 0<L, R \leq 3.10^6$