trailing-zero-problem-1

Given integer n, find length of n! (which is factorial of n) excluding trailing zeros.

Input

The first line of the standard input contains one integer t (t<10001) which is the number of test cases.

In each of the next t lines there is number n (0 ≤ n ≤ 5*10^9).

Output

For each test, print the length of n! (which is factorial of n).

Constraints

1 ≤ t ≤ 10
1 ≤ n ≤ 10^9

SAMPLE INPUT
3
5
7
10

SAMPLE OUTPUT
2
3
5

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from math import *
def Trailing_Zeroes(x):
	fives = 0
	i = 1
	while 5**i <= x:
		fives+=x/(5**i)
		i+=1
	return fives
t = int(input())
while t:
	t-=1
	n = int(input())
	a = 0
	#for i in xrange(1,n+1):
	 #   a+=log(i)
	print(int(ceil(lgamma(n+1)/log(10))) - Trailing_Zeroes(n))