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(n):
	ans=0
	m=5
	while (n>=m):
		ans+=n/m
		m*=5
	return ans
t=input()
while t:
	t-=1
	n=input()
	if (n==0 or n==1):
		print 1
	else:
		
		print int(math.ceil((math.log(math.sqrt(2*math.pi*n))+n*math.log(n/math.e))/math.log(10)))-zero(n)