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

• A₀ = 1
• A_n = A_n-1 + NOD(A_n-1) với i > 0

Trong đó, NOD(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 NOD: 1 2 4 7 9 12 18

Cho trước hai số nguyên dương A và B, đếm số lượng các phần tử trong dãy NOD 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 ≤ A ≤ B ≤ 100.000).

OUTPUT: 

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