FCTRHELL  Factor y Hell
Factorial(N) in base B : The number of trailing zeros.
Factorial(19) in base 9×10^0=9 can be written 725735500635080000, ending with 4 zeros.
Factorial(43) in base 2×10^1=20 can be written 59HHHFECFCCEGH5G7I7A3A8G88F8CD8G000000000, ending with 9 zeros.
What about working with serious constraints and tricky cases ?
Factorial(N) will be a huge one, the base will be dummy too and have the special form : B×10^E.
Input
The input begins with the number T of test cases in a single line.
In each of the next T lines there are three integers : N, B, E.
Output
For each test case, print the number of zeros at the end of Factorial(N) written in base B×10^E.
Example
Input: 3 19 9 0 43 2 1 10000 100 10 Output: 4 9 208
Constraints
1 <= T < 2000 1 <= N < 10^1000 1 <= B < 10^9 0 <= E < 10^9
Informations
Don't worry about the 'special' base 1 (B=1 and E=0), it is absent from input.
About distribution : random input (N : loguniform, B : uniform, E : uniform) in their range. Some tricky cases are added.
It is recommended to solve FACTBASE first, and find a way to solve
FCTRL much faster than common solutions.
Time limit is ×13.6 my best Python3 time, or ×1.33 my "basic" one.
hide comments
Min_25:
20140420 12:53:43
Nice problem. :)


Apoorv Jindal:
20131219 15:45:07
I am getting TLE. Cant see how I can optimize it further! Please suggest something.


abdou_93:
20130527 19:58:24
time limit exceeded ... time limit exceeded...:( not easy to solve this problem 

Michael Kharitonov:
20130315 12:54:07
Thank god O(N^2) per test is enought. I know how to solve it in O(N*log(N)^2), that would be real hell


[Rampage] Blue.Mary:
20130228 16:56:57
It's a boring constant optimization problem when using PIKE.


Ehor Nechiporenko:
20130206 12:30:25
Thanks a lot Franky)) Increasing cell size in long arithmetics was enough, but that's not all possible ways of optimizing.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130205 18:08:43
TLE.. It's not easy to do with C/C++! I should learn PIKE to solve this one!


Ehor Nechiporenko:
20130205 15:06:01
Great probmlem, Franky)) And now it's time for the optimizing trip to resolve this one.


:D:
20130204 13:57:04
I don't understand how is E uniform in it's range. Wouldn't that make pretty much all generated cases trivial? I'm probably missing something, but isn't the result always 0 for E > 1000?


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130203 21:57:49
great problem! but I'm weak to deal with big integer.. (B and E is no problem but N) and I'm weak to work with python too (because it's slow).. Hard as hell! :O

Added by:  Francky 
Date:  20130203 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 