Problem Statement

A positive integer is called a $k$-smooth number if none of its prime factors exceeds $k$. Given an integer $N$ and a prime $P$ not exceeding $100$, find the number of $P$-smooth numbers not exceeding $N$.

Constraints

• $N$ is an integer such that $1 \le N \le 10^{16}$.
• $P$ is a prime such that $2 \le P \le 100$.

Input

The input is given from Standard Input in the following format:

N P

Output

Print the answer as an integer.