You are one of ICPC participants and in charge of developing a library for multiprecision numbers and radix conversion. You have just finished writing the code, so next you have to test if it works correctly. You decided to write a simple, well-known factorial function for this purpose: \includegraphics{https://static.e-olymp.com/content/01/01e17d5669e3945b82ef6807ebcd7ea9a42be4fe.jpg} \textbf{M! = i = M × (M − 1) × ··· × 2 × 1, 0! = 1}. Your task is to write a program that shows the number of trailing zeros when you compute \textbf{M!} in base \textbf{N}, given \textbf{N} and\textbf{M}. \InputFile The input contains multiple data sets. Each data set is described by one line in the format below: \textbf{N M} where \textbf{N} is a decimal number between \textbf{8} and \textbf{36} inclusive, and \textbf{M} is given in the string representation in base \textbf{N}. Exactly one white space character appears between them. The string representation of \textbf{M} contains up to \textbf{12} characters in base \textbf{N}. In case \textbf{N} is greater than \textbf{10}, capital letters \textbf{A}, \textbf{B}, \textbf{C}, ... may appear in the string representation, and they represent \textbf{10},\textbf{11}, \textbf{12}, ..., respectively. The input is terminated by a line containing two zeros. You should not process this line. \OutputFile For each data set, output a line containing a decimal integer, which is equal to the number of trailing zeros in the string representation of \textbf{M!} in base \textbf{N}.