eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Числа Белла

Числа Белла

Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB

Число Белла 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 (0n, p10000). Відомо, що p – просте.

Вихідні дані

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

.

Приклад

Вхідні дані #1
1 5
3 2
4 2
4 3
10000 3
Вихідні дані #1
0
2
5
2
24962375