Hello, I am trying to solve this problem:

A positive integer is said to be k-smooth if none of its prime factors exceeds k. Compute how many positive integers less than or equal to N are k-smooth.

Input

The input contains multiple test cases (less than 50). Each test case consists of two lines. The first one contains an integer N (1 ≤ N ≤ 5,000,000), the second one an integer k (1 ≤ k ≤ 1000).

Output

For each test case output a single line with the corresponding answer.

Can anyone help me? thanks