Cho \(q\) truy vấn. Mỗi truy vấn cho hai số \(l, r\). Tính LCM của tất cả số từ \(l\) đến \(r\), modulo \(10^9+7\).

Định dạng đầu vào

• Dòng đầu: \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp: mỗi dòng \(l, r\) (\(1 \le l \le r \le 10^6\)).

Định dạng đầu ra

• \(q\) dòng, mỗi dòng là \(LCM(l,l+1,\dots,r) \bmod (10^9+7)\).

Ví dụ

Input:

2
1 3
2 5

Output:

6
60

Ràng buộc

• 100% số điểm: \(r \le 10^6\).