SGAME9

Xem PDF



Thời gian:
Java 5.0s
Bộ nhớ:
Java 512M

Tác giả:
Dạng bài
Điểm: 650 (p) Thời gian: 2.5s Bộ nhớ: 256M 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: table

Cho \(Q\) truy vấn, mỗi truy vấn gồm hai số nguyên dương \(A\)\(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 ≤ Q ≤ 10^5)\)
  • \(Q\) dòng tiếp theo, mỗi dòng là hai số nguyên dương \(A,B (1 ≤ A ≤ B ≤ 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\)

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


  • 0
    vinhntndu    2:52 p.m. 5 Tháng 8, 2020 đã chỉnh sửa

    Các số đầu tiên của tấm bảng sẽ như thế này

    1 2 4 8 16 ...
    2 4 8 16 77 ...
    3 6 12 33 66 ... 
    4 8 16 77 154 ...
    ....
    
    • 2 bình luận nữa