Đếm số


Submit solution


Points: 0.36 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem source:
VNOI Marathon '08 - Practice RoundProblem Setter: Khúc Anh Tuấn
Problem type

Với một số tự nhiên được viết trong hệ cơ số ~10~, ta định nghĩa vị trí xấu là vị trí mà chữ số tại đó với chữ số kề sau nó có độ chênh lệch không quá ~D~. Nếu một số có không quá ~K~ vị trí xấu thì đó là số đẹp.

Hãy đếm số lượng số đẹp trong khoảng từ ~A~ đến ~B~.

Input

Gồm một dòng duy nhất là ~4~ số nguyên ~A, B, D, K~ ~(1 \le A \le B \le 10^{15})~.

Output

Gồm một dòng duy nhất là số lượng số đếm được.

Sample Input

1 13 1 0

Sample Output

10

Comments