Count Non-Multiples

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 not 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 $X$ is not divisible by $K$.

Subtasks

• Subtask 1 (30 points):
  • $1 \le L \le R \le 10^{18}$.
  • $R-L \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

1 10 3

Output

7

Explanation

There are $10$ integers. Exactly $\lfloor10/3\rfloor=3$ are divisible by $3$, leaving $10-3=7$.

Example 2

Input

8 8 4

Output

0

Explanation

The interval contains only $8$, which is divisible by $4$, so the answer is $0$.

Example 3

Input

100 110 50

Output

10

Explanation

The interval has $11$ integers and only $100$ is divisible by $50$, so $10$ are not divisible.