FCTRL5 - Factorial (Again!)

Have you solved FCTRL problem? 

In this problem you need to do the same task (given positive integer n < 10100 you need to count number of zeroes at the end of the decimal number of n!), seems easy(?) but this time only Brainf**k language allowed.

Input

First line of input there is an integer T ≤ 1000 denoting number of test case.

Next T lines containing an integer n.

Each line is terminated with newline character (ASCII:10)

Output

For each test case, output number of zeroes at the end of the decimal form of number n!

Example

Input:
6
3
60
100
1024
23456
8735373

Output:
0
14
24
253
5861
2183837

Other Info

Input: 100% random log-uniform.
This problem is using custom judge, so you can see the detail after you get AC/WA.
Judge output format is like this: ("Code Length (Valid Command only)")"Cell Used"("BF Command executed").
Click here to see my submission result for this problem.
Judge output for my BF code is: (1340)501(392776170) meaning that my Valid BF commands = 1340 commands and My code using 501 BF cell and 392776170 commands executed.
You can click (AC/WA) status for more detail.
My code running time is 0.59s and using 1.6MB of memory.
Time limit is ~16× my BF program speed.


See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-07-15
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:BF
Resource:This Problem

hide comments
2017-03-09 10:05:51
Hi Robert,
You guys are really tremendous in the world of programming,I am a newbie would you please give me any advice or books to become like you,any advice will be sincerely asppreciated,looking forward for your reply!!
Regards,
Sawan
2013-07-24 01:14:10 (Tjandra Satria Gunawan)(曾毅昆)
@Robert Gerbicz: Congratulations, actually your code is faster than mine (9.15% faster than mine on my own BF interpreter), but unfortunately on bff 1.0.3.1 the longer your code is the slower your running time (see my commennt on BITCNTR problem). Hope you enjoyed this problem :-)
(gerrob) Yes, really enjoyed your problem, but you haven't answered to my request.
(tjandra) Sorry, I'm too busy recently. I'll set it on August.

Last edit: 2013-07-24 01:13:53
2013-07-23 16:18:17 Robert Gerbicz
Great problem, Tjandra, could you setup this problem in the challenge section? Score would be the number of BF commands executed.
Ans: Sound good :-) but this problem will stay in classical (I'll set new one). But for now, I don't have enough free time to set new problem (new judge too). I plan to add it before 11 August 2013, please be patient and sorry for inconvenience.
(gerrob): OK, thanks your work.
EDIT(tjandra): sorry I can't complete your request for now, maybe next time (I don't know exactly) I'll set that problem.

Last edit: 2013-08-31 22:21:35
2013-07-23 01:25:01 (Tjandra Satria Gunawan)(曾毅昆)
People may ask why I didn't solve FCTRL problem using Brainf**k, the answer is: that because my Brainf**k solution for that problem is too slow (or time limit is too strict for Brainf**k: 10^5 test case with 6sec time limit using pyramid cluster). I generate 10^5 worst case test case (fit on FCTRL constraints) on my pyramid tester problem and my current Brainf**k code (heavily optimized) run in 21sec (still 3.5× slower than FCTRL time limit), so I think it's impossible to solve FCTRL problem using Brainf**k with current time limit.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.