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.

Input

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

Output

Print the answer as an integer.

Constraints

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

Sample Input 1

36 3

Sample Output 1

14

The 3-smooth numbers not exceeding 36 are the following 14 integers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36.
Note that 1 is a k-smooth number for all primes k.

Sample Input 2

10000000000000000 97

Sample Output 2

2345134674

见题面 Input 部分

见题面 Output 部分