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 \leq b)\), xét số có dạng \(a \times (a + 1) \times ... \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...\times b\).

Input

• Dòng đầu ghi số nguyên dương \(T\) \((T \leq 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 \leq a \leq b \leq 10^6)\).

Output

• In ra \(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...\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\).

Example

2 
2 3
5 5

9
3

Ràng buộc

• Subtask \(1\) (\(30\%\) số điểm): Có \((1 \leq a \leq b \leq 10)\)
• Subtask \(2\) (\(30\%\) số điểm): Có \((a \leq b \leq 100)\)
• Subtask \(3\) (\(40\%\) số điểm): Có \((a \leq b \leq 10^6)\)