# Bell numbers

Very easy

Execution time limit is 0.5 seconds

Runtime memory usage limit is 64 megabytes

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

Input #1

Answer #1

Submissions 206

Acceptance rate 61%