Числа Белла

Число Белла B_n дорівнює кількості розбиттів множини з n елементів на довільну кількість не порожніх підмножин, що не перетинаються. Наприклад, B_3 = 5, оскільки існує 5 можливих розбиттів множини {a, b, c}: {{a}, {b}, {c}}, {{a, b}, {c}}, {{a, c}, {b}}, {{a}, {b, c}}, {{a, b, c}}. Додатково вважаємо, що B_0 = 1.

Розглянемо визначник D_n, вказаний на малюнку.

Для заданого простого числа p знайти найбільше ціле k, для якого D_n ділиться на p^k

.

Вхідні дані

Кожен рядок вводу містить два цілих числа n та p (0 ≤ n, p ≤ 10000). Відомо, що p – просте.

Вихідні дані

Для кожної пари вхідних значень n та p у окремому рядку вивести найбільше ціле k, для якого D_n ділиться на p^k

.

Приклади