Bội số chung nhỏ nhất của 2 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 ≤ 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 vào: Đọc từ tệp CAU4.INP có cấu trúc như sau:

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

  Kết quả: Ghi ra tệp CAU4.OUT 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.

Ví dụ:

CAU4.INP
    2
    3 4
    7 7 
CAU4.OUT
    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ố thỏa mãn: (1, 7); (7, 1); (7, 7).

Ràng buộc:

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