AmiZero - Số Không Ở Cuối
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: ami

Lưu ý : bài này chỉ khác phiên bản khó ở 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 = 1) 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 ≤ 105).

Output

Q dòng, mỗi dòng là một kết quả tương ứng.

Ví dụ

  • input
    1
    1 110 2 2
    output
    10

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ố.

Back to Top