Số tám may mắn

Xem PDF

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

bin9638 là một cậu học sinh rất có duyên với số \(8\), cậu có \(8\) người bạn gái, \(8\) năm học sinh giỏi, \(8\) cái máy tính,..... Bởi vậy từ lâu cậu đã coi số \(8\) là con số may mắn của đời mình.

Hôm nay trên lớp bin9638 được thầy giáo toán học algorit giảng bài về ước của các số, vậy nên bin9638 cũng đã nghĩ về một vấn đề toán học liên quan đến con số \(8\) của mình. Cậu tự hỏi nếu có \(1\) dãy số tự nhiên từ \(l\) đến \(r\) thì trong dãy đó có bao nhiêu số tự nhiên có đúng \(8\) ước nguyên dương.

bin9638 vì suy nghĩ bài toán này liên tiếp \(8\) ngày \(8\) đêm đến mất ăn mất ngủ mà vẫn chưa xong. Vì vậy các bạn hãy giúp cậu ấy nhé, nếu làm được thì sẽ được bin9638 tặng một món quà đấy !

Input

  • Dòng đầu tiên là số truy vấn \(Q\).
  • \(Q\) dòng tiếp theo mỗi dòng là hai số nguyên dương \(l\)\(r\).

Output

  • \(Q\) dòng là kết quả của các truy vấn tương ứng.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(Q \le 10\)\(l,r \le 10^5\).

  • Subtask \(2\) (\(30\%\) số điểm): \(Q \le 100\)\(l,r \le 10^7\).

  • Subtask \(3\) (\(40\%\) số điểm): \(Q \le 10^5\)\(l,r \le 10^7\).

Example

Test 1

Input
1
128 129
Output
1
Note

Chỉ có \(1\) số thỏa mãn là \(128\).


Bình luận


  • -22
    tuanha2    9:15 p.m. 30 Tháng 5, 2021

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


    • -22
      algorit    11:35 a.m. 31 Tháng 5, 2021

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

      3 bình luận nữa