Divisibility by 11

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

In this problem, your task is to count how many numbers in the range \([a; b]\) have a digit sum of at least \(p\) and at most \(q\), and are also evenly divisible by 11.

Input

The first line contains two integers \(a\) and \(b\).

The second line contains two integers \(p\) and \(q\).

Output

Print a single integer in a single line — the desired count of numbers.

Constraints

\(1 \le a \le b < 10^{18}\),

\(1 \le p \le q < 163\).

Samples

Input (stdin) сopy	Output (stdout) сopy
11 40 3 6	2

Notes

3 numbers from the specified range are divisible by 11 (11, 22, 33). Of these, only 2 numbers (22 and 33) have a digit sum that satisfies our requirements.