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\) và \(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\) và \(l,r \le 10^5\).

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

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

Example

1
128 129

1