Indivisibility of binomial coefficients

Let us denote , where 0 ≤ i ≤ n and n, i are integer numbers. Given a natural number n and a prime number p. You are required to find numbers of integers i from {0, 1, ..., n} such that C^i_n is not divisible by p.

Input

The only line of the input file consists of a natural number n ≤ 10^18 and a prime number p < 10^18.

Output

In the output file you should write the answer of the task.

Examples