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 đoạn 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