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 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~.

Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~), xét số có dạng ~a \times (a + 1) \times \dots \times b~. Hãy đếm có bao nhiêu cặp số nguyên ~x, y~ sao cho ~LCM(x, y) = a \times (a + 1) \times \dots \times b~.

Yêu cầu: Đếm số lượng cặp số nguyên dương ~(x, y)~ thỏa mãn điều kiện trên.

Input

• Dòng đầu ghi số nguyên dương ~T~ (~T \le 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~ (~1 \le a \le b \le 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 \times (a + 1) \times \dots \times 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

Sample Output 1

9
3