!

당신은 ICPC 참가자 중 한 명으로, 다정밀도 수와 진법 변환을 위한 라이브러리를 개발하는 일을 맡고 있다. 방금 코드 작성을 끝냈으니, 이제 이것이 올바르게 동작하는지 시험해 보아야 한다. 이를 위해 잘 알려진 간단한 팩토리얼 함수를 작성하기로 했다:

$M! = \prod_{i=1}^{M}{i} = M \times (M - 1) \times \cdots \times 2 \times 1, 0! = 1\text{.}$

당신의 임무는 N과 M이 주어졌을 때, M!을 N진법으로 계산했을 때의 뒤따르는 0의 개수를 출력하는 프로그램을 작성하는 것이다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식의 한 줄로 주어진다:

N M

여기서 N은 8 이상 36 이하의 십진수이고, M은 N진법의 문자열 표현으로 주어진다. 두 값 사이에는 정확히 하나의 공백 문자가 있다.

M의 문자열 표현은 N진법으로 최대 12자이다. N이 10보다 크면 문자열 표현에 대문자 A, B, C, ...가 나타날 수 있으며, 이들은 각각 10, 11, 12, ...를 나타낸다.

입력은 두 개의 0이 있는 줄로 끝난다. 이 줄은 처리하지 않는다.

각 데이터 세트에 대해, M!을 N진법으로 표현했을 때 뒤따르는 0의 개수와 같은 십진 정수를 한 줄에 출력한다.