問題文

2 以上 N 以下の整数のうち、K 種類以上の素因数を持つものの個数を求めてください。

制約

• 2 \leq N \leq 10^7
• 1 \leq K \leq 8
• 入力は全て整数

入力例 1

15 2

出力例 1

5

例えば、4=2^2 は素因数を 1 種類持つため条件を満たさず、 6=2\times 3 は素因数を 2 種類持つため条件を満たします。

条件を満たすのは、6,10,12,14,15 の 5 個です。

入力例 2

30 2

出力例 2

13

条件を満たすのは、6,10,12,14,15,18,20,21,22,24,26,28,30 の 13 個です。

入力例 3

200 4

出力例 3

0

入力例 4

869120 1

出力例 4

869119

入力例 5

10000000 3

出力例 5

6798027