Trong quá trình nghiên cứu giáo sư X phát hiện ra một loại số nguyên mới và đặt tên là số đặc biệt, một số nguyên dương \(n\ \)được gọi là số đặc biệt nếu \(n\) thỏa mãn hai tính chất sau:

1. \(n\) chia hết cho 3;

2. \(n\) có đúng 9 ước số.

Giáo sư X muốn khảo sát mật độ các số đặc biệt, nên nhờ các bạn tham gia thi chọn học sinh giỏi Tin học cấp tỉnh, lập trình giải quyết bài toán sau: “Cho hai số nguyên không âm \(a,\ b\), hãy đếm số lượng số đặc biệt trong đoạn \(\lbrack a,\ b\rbrack\).”

Dữ liệu vào:

• Dòng đầu chứa số nguyên T là số bộ dữ liệu;

  • \(T\) dòng sau, mỗi dòng chứa hai số nguyên dương\(\ a,\ b;a \leq b\). Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Kết quả:

• \(T\) dòng, mỗi dòng là số lượng số đặc biệt trong đoạn \(\lbrack a,\ b\rbrack\) tương ứng với bộ dữ liệu vào.

Ví dụ:

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài có \(a,\ b \leq \ 10^{3};\ T = \ 1;\)

• Có 25% số test ứng với 25% số điểm của bài có \(a,\ b \leq \ 10^{4};\ T\ \leq \ 100;\)

• Có 25% số test ứng với 25% số điểm của bài \(a,\ b \leq \ 10^{6};\ T = 10;\)

• Có 25% số test ứng với 25% số điểm còn lại của bài có \(a,\ b \leq \ 10^{6};\ T\ \leq \ 10^{5}.\)