Ký hiệu \(D(n)\) là số lượng ước số của số tự nhiên \(n\), ví dụ: \(D(10)=4\) và \(D(12)=6\). Với \(L\) và \(R\) cho trước \((L\leq R)\), hãy tính tổng \(D(L)+D(L+1)+...+D(R-1)+D(R)\).

Input

Dòng đầu chứa số nguyên dương \(T\leq 10^6\) là số lượng câu hỏi.

\(T\) dòng sau, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) thể hiện một câu hỏi \(\left(1\leq L\leq R\leq 10^6\right)\).

Output

Gồm \(T\) dòng, mỗi dòng chứa một số nguyên dương là câu trả lời cho câu hỏi tương ứng.

Ví dụ

Input

2
1 12
4 5

Output

35
5