!
Вы являетесь одним из участников 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.