Cho đoạn ~[a,b] (1 \le a \le b \le 10^9)~ hãy tính tổng tất cả các ước lẻ lớn nhất của tất cả các số trong đoạn ~[a,b]~

Input

Dòng đầu chứa số nguyên dương ~t~ là số bộ kiểm thử ~1 \le t \le 10^5~

Tiếp theo ~t~ dòng mỗi dòng hai số nguyên ~a,b~ thỏa mãn ~(1 \le a \le b \le 10^9)~

Output

Gồm ~t~ dòng mỗi dòng là kết quả 1 bộ kiểm thử

Ví dụ

Input

2
5 12
100 1000

Output

44
330077

Giải thích

Trong test đầu thì kết quả cần tính là ~5+3+7+1+9+5+11+3~ bằng ~44~