Have you solved FCTRL problem? 

In this problem you need to do the same task (given positive integer n < 10¹⁰⁰ 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