Given an arithmetic sequence a, a + d, a + 2*d, ..., a + n*d.

Request

Count the number of digit x appearing in the given sequence.

Input

- A line containing a, d, n, x.

Output

- The result found.

Example

Input:
10 5 2 0

Output:
2

Limitations

- 1 ≤ a, n ≤ 10⁹.
- 1 ≤ d ≤ 20,000.