問題文

$k$ 以下の素数のみを素因数に持つ正整数を $k$-smooth number と呼びます。
整数 $N$ および $100$ 以下の素数 $P$ が与えられるので、 $N$ 以下の $P$-smooth number の個数を求めてください。

制約

• $N$ は $1 \\le N \\le 10^{16}$ を満たす整数
• $P$ は $2 \\le P \\le 100$ を満たす素数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $P$

出力

答えを整数として出力せよ。

入力例 1

36 3

出力例 1

14

$36$ 以下の $3$-smooth number は $1,2,3,4,6,8,9,12,16,18,24,27,32,36$ の $14$ 個です。
$1$ は任意の素数 $k$ に対して $k$-smooth number であることに注意してください。

入力例 2

10000000000000000 97

出力例 2

2345134674