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
import math
def zero(x):
	p=1
	sumx=0
	y=x
	while y>0:
		p=p*5;
		y=x/p;
		sumx=sumx+y;
	return sumx	
	
def main():
	pi=3.14159265358979323
	e=2.71828182845904523536 
	T=input()
	for i in range (0,T):
		n=input()
		if(n==0 or n==1 ):
			print 1
			continue
		num=int(0.5*math.log10(2*pi)+((n+0.5)*(math.log10(n)))-(n*math.log10(e))+(math.log10(e)/(12*n)))+1
		x=num-zero(n)
		print x
	return 0

if __name__ == '__main__':
	main()