Số phong phú

Trong số học, số phong phú là các số mà tổng các ước số tự nhiên của số đó (không kể chính nó) lớn hơn nó. Ví dụ:

• Số 12 có tổng các ước số (không kể 12) là $1 + 2 + 3 + 4 + 6 = 16 > 12$. Do đó 12 là một số phong phú.
• Số 10 có tổng các ước (không kể 10) là $1 + 2 + 5 = 8 < 10$ nên 10 không phải là một số phong phú.

Yêu cầu: cho $Q$ trường hợp, mỗi trường hợp gồm 2 số nguyên dương $L, R$ $(L \le R \le 10^5)$. Với mỗi trường hợp, hãy xác định số lượng số phong phú trong đoạn $[L, R]$.

Đọc vào từ file RICHNUM.INP

• Dòng đầu tiên chứa số nguyên dương $Q$ xác định số trường hợp.
• $Q$ dòng tiếp theo, dòng thứ $i$ chứa 2 số nguyên dương $L, R$ xác định yêu cầu trường hợp thứ $i$.

Ghi ra file RICHNUM.OUT gồm $Q$ dòng, dòng thứ $i$ là một số nguyên xác định số lượng số phong phú nằm trong đoạn $[L, R]$ tương ứng yêu cầu trường hợp thứ $i$ trong file dữ liệu vào.

• 40% số test tương ứng 40% số điểm có $Q = 1; 0 < L \le R \le 10^3$
• 20% số test khác tương ứng 20% số điểm có $Q = 1; 0 < L \le R \le 10^5$
• 20% số test khác tương ứng 20% số điểm có $1 < Q \le 100; 0 < L \le R \le 10^5$
• 20% số test còn lại tương ứng 20% số điểm có $1 < Q \le 10^5; 0 < L \le R \le 10^5$