Bài 9: Thế giới Số Phong Phú

Yêu cầu: Một số nguyên dương ~N~ được gọi là "Số phong phú" nếu tổng các ước số thực sự của nó (không tính chính nó) lớn hơn chính nó. Ví dụ: ~12~ có các ước thực sự là ~1, 2, 3, 4, 6~. Tổng = ~16 > 12 \rightarrow 12~ là số phong phú. Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số ~L~ và ~R~. Hãy đếm số lượng "Số phong phú" nằm trong đoạn ~[L, R]~.

Giới hạn:

• ~1 \le Q \le 10^5~
• ~1 \le L \le R \le 10^6~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (Input):

• Dòng đầu tiên chứa số lượng truy vấn ~Q~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~.

Dữ liệu ra (Output):

• In ra ~Q~ dòng, mỗi dòng là số lượng Số phong phú trong đoạn tương ứng.

Ví dụ: Input:

1
10 15

Output:

1

(Giải thích: Trong đoạn ~[10, 15]~, chỉ có số ~12~ là Số phong phú.)