Trong số học, bội số chung nhỏ nhất (hay còn gọi tắt là bội chung nhỏ nhất), viết tắt là BCNN (tiếng Việt) hay LCM (Least Commmon Multiple/ Lowest Common Multiple - Tiếng Anh) của hai số nguyên ~x~ và ~y~ là số nguyên dương nhỏ nhất chia hết cho cả ~x~ và ~y~.

Yêu cầu: Cho hai số nguyên dường ~a~ và ~b (a ≤ b)~, xét số có dạng ~a × (a + 1) × ... × b~. Hãy đếm có bao nhiêu cặp số nguyên ~x, y~ sao cho ~LCM(x, y) = a × (a + 1) × ... × b~.

Input

• Dòng đầu ghi số nguyên dương ~T ≤ 10~ là số lượng bộ dữ liệu.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a, b~.

Giới hạn:

• Có 30% số điểm ứng với các test có ~1 ≤ a ≤ b ≤ 10~.
• Có 30% số điểm ứng với các test có ~a ≤ b ≤ 100~.
• Có 40% số điểm ứng với các test có ~a ≤ b ≤ 10^6~.

Output

• Gồm T dòng, mỗi dòng là số cặp số nguyên dương ~(x, y)~ sao cho ~LCM(x, y) = a × (a + 1) × ... × b~. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho ~10^9 + 7~.

Sample

Input #1

2
2 3
5 5

Output #1

9
3

Problem source: Kc97ble - Free Contest 40