Bell numbers

A Bell number B_n is equal to the quantity of ways, in which a set of n elements can be partitioned into disjoint non-empty subsets. For example, B_3 = 5, because we have 5 possible partitions of the set {a, b, c}: {{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}}, {{a, b, c}}.

Additionally consider, that B_0 = 1.

Regard a determinant D_n, given on the figure.

For a given prime number p find the greatest integer k, for which D_n is divisible by p^k

.

Input

Each line of input contains two integers n and p (0 ≤ n, p ≤ 10000). It is known, that p is prime.

Output

For each pair of input values n and p on a separate line output the greatest integer k, for which D_n is divisible by p^k

Examples