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 1 bài toán rất thú vị. Bình quy ước "Số đẹp" là số không chứa 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 2 số nguyên dương ~a, b~ (~a < b~). Đặt ~S = a \times (a+1) \times ... \times b~. 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 1 số đẹp.

Ví dụ: Với ~a = 4, b = 15~ thì ~S = 4 \times 5 \times 6 \times ... \times 15 = 217945728000~ 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 số 0 tận cùng của ~S~ cần xóa để ~S~ trở thành số đẹp.

Input

• Dòng đầu tiên 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 chứa một số nguyên dương ~a~, ~b~ (~1 \le a \le 10^{16}~).

Output

• Ghi ra ~T~ dòng, mỗi dòng ghi số lượng chữ số ~0~ tận cùng của ~S~ tương ứng. Kết quả có thể rất lớn nên cần chia lấy dư cho ~10^9 + 7~.

Sample Input

4
1 6
1 10
2 4
10 20

Sample Output

1
2
0
3

Subtasks

• 40% số test với ~1 \le T \le 10; a < b \le 18~
• 30% số test với ~T = 1; a < b \le 10^6~
• 20% số test với ~1 < T \le 10^4; a < b \le 10^5~
• 10% số test với ~10^4 < N \le 10^5; a < b \le 10^{16}~