题目描述

如果一个正整数的质因数都不超过 $k$，则称其为 $k$ 光滑数。
给定一个整数 $N$ 和一个不超过 $100$ 的质数 $P$，找出不超过 $N$ 的 $P$ 光滑数的个数。

约束条件

• $N$ 是一个整数，满足 $1 \le N \le 10^{16}$。
• $P$ 是一个质数，满足 $2 \le P \le 100$。

输入

输入以以下格式从标准输入中给出：

$N$ $P$

输出

输出作为一个整数。

示例输入 1

36 3

示例输出 1

14

不超过 $36$ 的 $3$ 光滑数一共有 $14$ 个：$1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36$。
请注意，对于所有的质数 $k$，$1$ 都是 $k$ 光滑数。

示例输入 2

10000000000000000 97

示例输出 2

2345134674