Số đẹp

Bình và An đang tích cực học tập, ôn luyện để thi vào trường THPT chuyên trong tỉnh. Trong quá trình giải các bài toán, Bình đã gặp và giải một bài toán rất thú vị.

Bình quy ước "Số đẹp" là số không có chữ số \(0\) tận cùng.

Bình muốn thử năng lực học tập của An nên thách đố An giải bài toán sau:

Cho hai số nguyên dương \(a, b\) \((a < b)\). Đặt

Hãy cho biết số lượng chữ số \(0\) tận cùng của \(S\) cần xóa để \(S\) trở thành một số đẹp.

Ví dụ: với \(a = 4\), \(b = 15\) thì

nên số lượng chữ số \(0\) tận cùng cần xóa là \(3\).

Rất nhanh chóng An đã tìm ra kết quả, em hãy lập trình để cùng bạn An đối sánh kết quả với Bình nhé!

Yêu cầu. Đếm số lượng chữ số \(0\) tận cùng của \(S\) cần xóa để \(S\) trở thành số đẹp.

Input

• Dòng thứ nhất chứa số nguyên \(T\) \((1 \le T \le 10^5)\) là số lượng cặp số nguyên;

• \(T\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương \(a, b\) \((a < b \le 10^{16})\).

Output

Ghi ra \(T\) dòng, mỗi dòng ghi số lượng chữ số \(0\) tận cùng tương ứng. Kết quả của mỗi dòng lấy modulo \(10^9 + 7\).

Scoring

• (\(40\%\)) \(1 \le T \le 10\), \(a < b \le 18\);

• (\(30\%\)) \(T = 1\), \(a < b \le 10^5\);

• (\(20\%\)) \(1 < T \le 10^4\), \(a < b \le 10^5\);

• (\(10\%\)) \(10^4 < T \le 10^5\), \(a < b \le 10^{16}\).