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 : log-uniform, 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.


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

hide comments
2013-02-03 21:57:49 (Tjandra Satria Gunawan)(曾毅昆)
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
--ans--> It's not so hard to solve, 'hell' is here just because in French factorial sounds 'factor y hell', that's all. But find tricky cases was the best part for me. If N was 'small' there were no interest at all. Thanks for your comment.
Edit : and in C, it's not so difficult to implement an efficient one-word-division, so it's very accessible too.
Good luck to everybody.

Last edit: 2013-02-03 22:12:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.