Count Multiples in an Interval

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive integers $L,R,K$ with $L\le R$, count the integers in $[L,R]$ that are divisible by $K$.

Input

One line contains three positive integers $L$, $R$, and $K$.

Output

Print the number of integers $X$ satisfying $L\le X\le R$ and $K\mid X$.

Subtasks

• Subtask 1 (30 points):
  • $1 \le L \le R \le 10^6$.
  • $1 \le K \le 10^{18}$.
• Subtask 2 (70 points):
  • $1 \le L \le R \le 10^{18}$.
  • $1 \le K \le 10^{18}$.

Examples

Example 1

Input

5 20 4

Output

4

Explanation

The multiples in the interval are $8,12,16,20$, so the answer is $4$.

Example 2

Input

1 10 20

Output

0

Explanation

The smallest positive multiple of $20$ is $20>10$, so the answer is $0$.

Example 3

Input

1000000000000 1000000000100 25

Output

5

Explanation

The multiples are $10^{12}$, $10^{12}+25$, $10^{12}+50$, $10^{12}+75$, and $10^{12}+100$, for a total of $5$.