Bội số chung nhỏ nhất của hai số nguyên dương ~x~ và ~y~ là số nguyên dương nhỏ nhất chia hết cho cả ~x~ và ~y~, kí hiệu ~LCM(x, y)~.

Cho hai số nguyên dương ~a~ và ~b~ ~(a \le b)~.

Yêu cầu

Hãy đếm số cặp số nguyên dương ~x,\ y~ sao cho ~LCM(x, y)~ bằng tích các số nguyên liên tiếp từ ~a~ đến ~b~ (trường hợp ~a~ bằng ~b~ thì tích này bằng ~a~).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu ghi số nguyên dương ~T~ ~(T \le 10)~ là số test.
• ~T~ dòng tiếp theo, mỗi dòng là một test chứa hai số nguyên dương ~a,\ b~ ~(1 \le a \le b \le 10^6)~.

Dữ liệu đầu ra

Gồm ~T~ dòng, mỗi dòng là phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.

Ràng buộc dữ liệu

• Có 40% số điểm của bài có ~a, b \le 10~;
• Có 30% số điểm tiếp theo của bài có ~a, b \le 100~;
• Có 30% số điểm còn lại của bài không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

2
3 4
7 7

OUTPUT

15
3

Giải thích:

• Test 1 có ~15~ cặp số thỏa mãn: ~(1, 12)~; ~(2, 12)~; ~(3, 4)~; ~(3, 12)~; ~(4, 3)~; ~(4, 6)~; ~(4, 12)~; ~(6, 4)~; ~(6, 12)~; ~(12, 1)~; ~(12, 2)~; ~(12, 3)~; ~(12, 4)~; ~(12, 6)~; ~(12, 12)~.
• Test 2 có ~3~ cặp số số thỏa mãn: ~(1, 7)~; ~(7, 1)~; ~(7, 7)~.