Remainder Count - Repovive Starter Round 6 | Repovive

19A. Remainder Count

500 pts1s256 MB

You are given three integers $n$ , $d$ , and $r$ .

Count the integers $x$ that satisfy both of the following conditions:

$0 \le x \le n$ ;
the remainder when $x$ is divided by $d$ is $r$ .

Constraints

$1 \le n,d \le 10^9$
$0 \le r < d$

Input

The input contains three integers $n$ , $d$ , and $r$ .

n \quad d \quad r

Output

Output the number of integers $x$ that satisfy the given conditions.

answer

Samples

Input

10 3 1

Explanation

The valid integers are $1$ , $4$ , $7$ , and $10$ , so the answer is $4$ .

Output

Input

5 7 6

Explanation

The smallest non-negative integer with remainder $6$ after division by $7$ is $6$ , which is greater than $5$ . Therefore, no valid integer exists.

Output

Input

8 4 0

Explanation

The valid integers are $0$ , $4$ , and $8$ , so the answer is $3$ .

Output

You are given three integers $n$ , $d$ , and $r$ .

Count the integers $x$ that satisfy both of the following conditions:

$0 \le x \le n$ ;
the remainder when $x$ is divided by $d$ is $r$ .

$1 \le n,d \le 10^9$
$0 \le r < d$

The input contains three integers $n$ , $d$ , and $r$ .

n \quad d \quad r

Output the number of integers $x$ that satisfy the given conditions.

answer

The valid integers are $1$ , $4$ , $7$ , and $10$ , so the answer is $4$ .

The smallest non-negative integer with remainder $6$ after division by $7$ is $6$ , which is greater than $5$ . Therefore, no valid integer exists.

The valid integers are $0$ , $4$ , and $8$ , so the answer is $3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19A. Remainder Count

Constraints

Input

Output

Samples

19A. Remainder Count

Constraints

Input

Output

Samples