Dãy số CODI

Dãy số CODI được xây dựng như sau:

• $A_0=1$;
• $A_n=A_{n-1}+\text{CODI}(A_{n-1})$ với $n>0$.

Trong đó, $\text{CODI}(x)$ là số lượng các ước dương của $x$.

Ví dụ một vài phần tử đầu tiên của dãy CODI: $1,2,4,7,9,12,18$.

Yêu cầu: Cho trước hai số nguyên dương $A$ và $B$, đếm số lượng các phần tử trong dãy CODI thuộc đoạn $[A,B]$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $T$ ($T<100000$): số lượng truy vấn.
• $T$ dòng sau, mỗi dòng chứa hai số nguyên $A,B$ ($1\le A\le B\le 100000$).

Dữ liệu ra

Gồm $T$ dòng, dòng thứ $i$ là số lượng phần tử của dãy CODI thuộc đoạn $[A,B]$ của truy vấn thứ $i$.

Ràng buộc

• $1\le T<100000$.
• $1\le A\le B\le 100000$.

Subtasks

• $60\%$ số test: $1\le A\le B\le {10}^3$.
• $40\%$ số test còn lại: $1\le A\le B\le {10}^5$.

Ví dụ