Số đẹp

Bình và An đang ôn thi vào trường THPT chuyên. Bình định nghĩa "số đẹp" là số không có chữ số 0 ở tận cùng. Cho hai số nguyên dương \(a, b\) (\(a < b\)), đặt \(S = a \times (a+1) \times \cdots \times b\). Hãy đếm số chữ số 0 tận cùng của \(S\) cần xóa để \(S\) trở thành số đẹp.

Input

Tệp SODEP.INP gồm:

• Dòng 1: Số nguyên \(T\) (\(1 \leq T \leq 10^5\)) - số lượng test cases
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số \(a, b\) (\(a < b \leq 10^{16}\))

Output

Tệp SODEP.OUT gồm \(T\) dòng, mỗi dòng là số chữ số 0 tận cùng của \(S\) tương ứng, lấy modulo \(10^9 + 7\).

Example

4
1 6
1 10
2 4
10 20

1
2
0
3

Scoring

• 40% test: \(T \leq 10\), \(b \leq 18\)
• 30% test: \(T = 1\), \(b \leq 10^5\)
• 20% test: \(T \leq 10^4\), \(b \leq 10^5\)
• 10% test: \(T \leq 10^5\), \(b \leq 10^{16}\)