!#3620
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:
M! = M \times (M - 1) \times \cdots \times 2 \times 1, 0! = 1.
Your task is to write a program that shows the number of trailing zeros when you compute in base , given and .
The input contains multiple data sets. Each data set is described by one line in the format below:
where is a decimal number between and inclusive, and is given in the string representation in base . Exactly one white space character appears between them. The string representation of contains up to characters in base . In case is greater than , capital letters , , , ... may appear in the string representation, and they represent , , , ..., respectively.
The input is terminated by a line containing two zeros. You should not process this line.
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 in base .
1-nji mysal