Count Multiples in a Prefix

Version: Phuoc Hung OJ Extended

Problem Statement

Given positive integers $N$ and $K$, consider the integers from $1$ to $N$. An integer is a multiple of $K$ if it is divisible by $K$. Count the multiples of $K$ in $[1,N]$.

Input

One line contains two positive integers $N$ and $K$.

Output

Print the number of integers $X$ satisfying $1\le X\le N$ and $K\mid X$.

Subtasks

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

Examples

Example 1

Input

20 3

Output

6

Explanation

The multiples not exceeding $20$ are $3,6,9,12,15,18$, so the answer is $6$.

Example 2

Input

7 10

Output

0

Explanation

The smallest positive multiple of $10$ is $10>7$, so there are no valid integers.

Example 3

Input

1000000000000000000 1000000000

Output

1000000000

Explanation

We have $10^{18}\div 10^9=10^9$, hence there are exactly $10^9$ multiples.