inftab

Xem PDF
Tác giả:
vinhntndu
Dạng bài
Điểm: 700 Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một bảng có số hàng và số cột là vô hạn. Các giá trị của các ô trong bảng được tính theo các quy tắc sau: Với \(i\) là chỉ số hàng, \(j\) là chỉ số cột, ta có:

  • \(A[i][1] = i\)
  • \(A[i][j] = A[i][j-1] + INV(A[i][j-1])\) \(\forall j > 1\)

Với \(INV(A)\) là hàm đảo ngược số \(A\). Ví dụ, \(INV(104) = 401, INV(200) = 002 = 2\).

Các số đầu tiên của bảng:

Cho \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(A\) và \(B\). Bạn hãy đếm số lần xuất hiện các số trong khoảng \([A,B]\) trên bảng đó.

Input

  • Dòng đầu tiên là số nguyên dương \(Q\), số lượng truy vấn \((1 \le Q \le 10^5)\)
  • \(Q\) dòng tiếp theo, mỗi dòng là hai số nguyên dương \(A,B (1 \le A \le B \le 10^{10})\)

Output

  • Gồm \(Q\) dòng, mỗi dòng là kết quả của truy vấn.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(A,B\) \(\leq\) \(10^6\)
  • Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm

Example

Test 1

Input 
2
1 3
4 8
Output 
4
11
Note
  • Trong khoảng [1;3], số 1 xuất hiện 1 lần, số 2 xuất hiện 2 lần, số 3 xuất hiện 1 lần nên tổng số lần xuất hiện là 4
  • Trong khoảng [4;8], số 4 xuất hiện 3 lần, số 5 xuất hiện 1 lần, số 6 xuất hiện 2 lần, số 7 xuất hiện 1 lần, số 8 xuất hiện 4 lần nên tổng số lần xuất hiện là 11

Bình luận


  • -7
    Ling212003    5:05 p.m. 7 Tháng 10, 2020 ← đã chỉnh sửa

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


    • 1
      vinhntndu    5:35 p.m. 7 Tháng 10, 2020

      K


      • -6
        THOANGLQDT    6:43 p.m. 26 Tháng 10, 2020

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


        • 3
          MinhNhan2010    8:03 a.m. 2 Tháng 11, 2021

          BẠN PHẢI TỰ VIẾT CODE ĐI CHỨ. BẠN ĐÃ NỘP ĐÂU MAK NÓI VIẾT EDTORIAL HẢ BẠN?


          • 3
            vinhntndu    7:46 p.m. 26 Tháng 10, 2020

            🙂 cứ từ từ


            • -5
              THOANGLQDT    8:48 a.m. 1 Tháng 11, 2020

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


              • -5
                THOANGLQDT    8:48 p.m. 29 Tháng 10, 2020 ← đã chỉnh sửa

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


                • 3
                  MinhNhan2010    6:17 p.m. 1 Tháng 11, 2021 ← đã chỉnh sửa

                  Sorry


                  • 4
                    dang7rickroll    10:07 p.m. 1 Tháng 11, 2021

                    cẩn thận lời ăn tiếng nói tí bạn ơi, không hay đâu !


                    • 4
                      jumptozero    9:27 p.m. 1 Tháng 11, 2021

                      Bạn ơi, ở đâu có nhiều thầy cô và các anh chị lớn tuổi, nên bạn chú ý ngôn từ nhé ! Cảm ơn bạn !


                      • 7
                        MinhNhan2010    8:03 a.m. 2 Tháng 11, 2021

                        sorry hai anh ạ. Em sẽ rút kinh nghiệm ạ. Em cảm ơn hai anh nhiều ạ

          3 bình luận nữa