Factorial Trailing Zeroes

Problem #292

Tags: interviews puzzle arithmetic

Who solved this?

No translations... yet

Thanks to my colleague Ivan Bannikov for help with general solution of this problem!

Very common exercise I've met on various IT-job interviews (both for programming and software testing positions) was about zeroes at the end of factorial. Usually it sounds like "How many consequtive zeroes 100! has at the end".

This is surely too easy, moreover that some modern languages handle long numbers "out of the box". Let us make it bit harder.

Given some value N, please tell, how many such trailing zeroes at the end will have its factorial N! if written in the non-decimal numeral system with the base B.

Input data will contain number of testcases in the first line.
Next lines will have N and B each.
Output should contain amount of trailing zeroes for every case.

Example:

input data:
3
10 10
659 385
6213 5054

answer:
2 64 172
You need to login to get test data and submit solution.