Số bất thường 2
Xem dạng PDFCái đẹp trong mắt mỗi người là khác nhau và Gấu cũng thế, Gấu say mê với những con số đẹp (tất nhiên là cũng có con gái đẹp). Con số theo Gấu là đẹp được định nghĩa như sau:
Một số nguyên dương $X$ gọi là số bất thường nếu nó thỏa tổng chữ số và tổng ~wibu~ của các chữ số thì nguyên tố cùng nhau. Người ta định nghĩa một hàm ~wibu(i) = 1^2+2^2+...+i^2~ với ~1 \leq i \leq 9~. Còn ~wibu(x)~ với số ~x = x_1x_2...x_k~ thì bằng tổng của ~wibu(x_1) + ... + wibu(x_k)~.
Ví dụ số $20$ có tổng chữ số là $2$, tổng wibu chữ số là $5$ là hai số nguyên tố cùng nhau nên $20$ là số bất thường.
Để phục vụ cho việc gì đó, mỗi ngày trong ~Q~ ngày Gấu cần phải tính tổng số bất thường trong đoạn ~[L, R]~. Bạn hãy giúp Gấu nhé.
Dữ liệu vào
- Dòng đầu tiên gồm số nguyên ~Q~ ~(1 \leq Q \leq 10^5)~.
- ~Q~ dòng sau, mỗi dòng gồm ba số nguyên ~L, R~ ~(1 \leq L \leq R \leq 10^{18})~.
Dữ liệu ra
Gồm ~Q~ dòng là đáp án của ~Q~ câu hỏi chia dư cho ~10^9+2709~.
Ví dụ
Input
2
19 20
1 100
Output
20
3268
Tính điểm
- Subtask 1 (30% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^6~.
- Subtask 2 (40% số điểm): ~1 \leq Q \leq 3, 1 \leq L \leq R \leq 10^{18}~.
- Subtask 3 (30% số điểm): Không có ràng buộc gì thêm.
Bình luận
Bài này MOD = 1e9+2709
bài này có MOD cho gì không anh sao em thấy mấy trang khác nó MOD cho 1e9+7 mà em cũng AC r mà này cũng không được ạ