Bài 11: Số Siêu Phong Phú

Yêu cầu: Một số nguyên dương ~X~ được gọi là "Siêu phong phú" nếu tổng các ước số của nó (bao gồm cả chính nó) là một số lẻ. Cho ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L, R~. Hãy đếm xem trong đoạn ~[L, R]~ có bao nhiêu số là số "Siêu phong phú".

Giới hạn:

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

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

• Dòng đầu tiên là 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ố Siêu phong phú nằm trong đoạn ~[L, R]~.

Ví dụ: Input:

1
1 10

Output:

5

(Giải thích: Trong đoạn ~[1, 10]~ có 5 số Siêu phong phú là: ~1, 2, 4, 8, 9~.