{"code":"demso","name":"Đếm Số Trong Đoạn","description":"**Nezuko** là $1$ cô bé xinh đẹp, dễ thương, là em gái quốc dân, crush trong mơ của bao thằng wibu. Hôm nay **Nezuko** đã khám phá ra số “**Wibu**”. Số “**Wibu**” là $1$ số tự nhiên mà tổng các chữ số nguyên tố cùng nhau với tổng $wibu$ của các chữ số với $wibu(i)=$$1^2+2^2+…+i^2$ $(0 \\leq i \\leq 9)$.  \r\n\r\n\r\nVí dụ số $20$, có tổng các chữ số là $2+0=2$ và tổng $wibu=wibu(2)$$+wibu(0)=5$ nguyên tố cùng nhau nên  là số “**Wibu**”. Còn số $33$ có tổng các chữ số là $3+3=6$ và tổng $wibu=wibu(3)$$+wibu(3)=28$ không nguyên tố cùng nhau nên không phải. \r\n\r\n\r\n  [user:bin9638] cũng là $1$ người crush **Nezuko** lâu năm. Bây giờ [user:bin9638] đang muốn tính tổng các số “**Wibu**” trong đoạn từ $l$ đến $r$ $(l,r \\leq 10^{18})$ để lấy le với **Nezuko**, nhưng khổ nỗi bây giờ [user:bin9638] đang mãi hóng movie mới của **Kimetsu No Yaiba** nên không có thời gian tính toán. Các bạn hãy giúp [user:bin9638] nhé. \r\n\r\nVì kết quả có thể rất lớn nên các bạn hãy in kết quả chia lấy dư cho **$10^9+7$**.\r\n\r\n\r\n#### Yêu cầu:\r\n- Tính tổng các số “**Wibu**” trong đoạn $[l,r]$\r\n\r\n#### Input\r\n+ Dòng đầu tiên là số truy vấn $q$ $(q ≤ 10^5)$.\r\n+ $q$ dòng tiếp theo mỗi dòng là $2$ số $l,r$.\r\n\r\n#### Output\r\n- Gồm $q$ dòng, mỗi dòng là kết quả cho truy vấn tương ứng.\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$ ($40\\%$ số điểm): $l,r \\leq 10^6$, $q ≤ 10$.\r\n\r\n- Subtask $2$ ($60\\%$ số điểm): không có ràng buộc gì thêm.\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2\r\n        19 20\r\n        1 100\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        20\r\n        3268\r\n        ```","points":2300.0,"partial":true,"time_limit":3.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}