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 ~i > 0~

Trong đó, ~\text{CODI}(x)~ = 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]~.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T < 100.000~) – Số lượng test trong file input.
• ~T~ dòng sau, mỗi dòng chứa cặp ~A, B~ (~1 \le A \le B \le 100.000~).

Output

• Gồm ~T~ dòng, mỗi dòng là kết quả của bài toán.

Sample Input 1

3
1 18
1 100
3000 4000

Sample Output 1

7
20
87