Đếm Số Trong Đoạn

Xem PDF

Điểm: 2300 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Nezuko\(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)\).

Ví 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.

bin9638 cũng là \(1\) người crush Nezuko lâu năm. Bây giờ 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ờ 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 bin9638 nhé.

Vì 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\).

Yêu cầu:

  • Tính tổng các số “Wibu” trong đoạn \([l,r]\)

Input

  • Dòng đầu tiên là số truy vấn \(q\) \((q ≤ 10^5)\).
  • \(q\) dòng tiếp theo mỗi dòng là \(2\) số \(l,r\).

Output

  • Gồm \(q\) dòng, mỗi dòng là kết quả cho truy vấn tương ứng.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(l,r \leq 10^6\), \(q ≤ 10\).

  • Subtask \(2\) (\(60\%\) số điểm): không có ràng buộc gì thêm.

Example

Test 1

Input
2
19 20
1 100
Output
20
3268

Bình luận


  • -2
    lequangtrung123 8:05 a.m. 4 Tháng 10, 2023

    xin loi bai khong xam va rat educational a


    • -4
      lequangtrung123 6:21 p.m. 3 Tháng 10, 2023

      bài xàm, phải code tà đạo như solution thì mới ac


      • 2
        161007thanhhiu 8:37 a.m. 21 Tháng 9, 2023

        :v ad ban mấy acc copy paste đi


        • -1
          anhthu030412 9:02 a.m. 24 Tháng 8, 2023

          Đọc câu đầu tiên nó cứ sao sao ă :))


          • 12
            BETTER 9:29 p.m. 3 Tháng 1, 2021

            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. NHÁ=))))

            1 phản hồi

            • 4
              ekhoavvdd 2:22 p.m. 31 Tháng 12, 2020

              mới cái anh em wibu vào làm :))


              • -1
                THOANGLQDT 9:38 p.m. 30 Tháng 10, 2020

                HEY anh kha


                • -1
                  TienMinh13042009 8:01 a.m. 2 Tháng 10, 2020

                  á hự


                  • 1
                    nguyenquochuy 6:25 p.m. 17 Tháng 9, 2020

                    đọc câu đầu trầm cảm 😢


                    • -16
                      donhatnam 9:51 a.m. 14 Tháng 9, 2020

                      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.