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

!

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

Ви є одним з участників ICPC і відповідаєте за разробтку бібліотеки довгої арифметики для роботи з числами у різних системах числення. Ви тільки що завершили писать свій код, так що тепер на наступному етапі ви повинні перевірити, чи працює він вірно. Ви вирішили з цією метою написати просту, широко відому функцію факторіалу:

M! = i = M × (M − 1) × ··· × 2 × 1, 0! = 1.

Ваша задача написати програму, яка показує кількість нулів після обчислення M! у системі числення з основою N, для заданих чисел N та M.

Вхідні дані

Вхід містить декілька наборів даних. Кожен набір даних описано одним рядком у ​​форматі, наведеному нижче:

N M

де N являє собою десяткове число від 8 до 36 включно, а M – рядкове подання заданого числа у системі числення N. Числа відокремлено рівно одним символом пропусу. Рядкове подання числа M містить до 12 символів у системі числення N. У випадку, якщо N більше 10, то латинські великі літери A, B, C, ... подають цифри 10, 11, 12, ..., відповідно.

Вхідні дані завершуються рядком, який містить два нулі, цей рядок не потрібно опрацьовувати.

Вихідні дані

Для кожного набору даних, отриманих на вході, виведіть рядок, який містить десяткове число, рівне кількості кінцевих нулів у рядку подання M! у системі числення з основою N.

Приклад

Вхідні дані #1
10 500
16 A
0 0
Вихідні дані #1
124
2
Джерело ACM-ICPC Japan Alumni Group Summer Camp 2007, Day 2, Tokyo, Japan, 2007-09-23