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], указанный на рисунке.

prb97

Для заданного простого числа p найти наибольшее целое k, для которого D[n] делится на p[k].

Входные данные

Каждая строка ввода содержит два целых числа n и p (0 ≤ n, p ≤ 10000). Известно, что 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