Lưu ý : bài này chỉ khác phiên bản dễ ở giới hạn của dữ liệu
Ami một dãy số nguyên dươngliên tiếp từ l đến r. LN lại cho Ami 2 số t và k. Cần đếm xem có bao nhiêu số nguyên x thoả mãn
1) l ≤ x ≤ r
2) xt có đúng k chữ số 0 tận cùng
Input
Dòng đầu tiên là số nguyên dương q (q ≤ 300000) biểu diễn một bộ số.
Q dòng tiếp theo, mỗi dòng là 4 số nguyên dương l , r , t , k (l , r , t , k ≤ 1017).
Output
Q dòng, mỗi dòng là một kết quả tương ứng.
Giải thích
Các số thoả mãn điều kiện là 10 , 20 , 30 , 40 , 50 , 60 , 70 , 80 , 90 , 110. Có 10 số.