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
t = int(raw_input())
pi = 3.141592653589793
while t>0:
	t-=1
	n = int(raw_input())
	if n==0 or n==1 or n==2 or n==3:
		print 1
		continue
	ans = math.floor((math.log(2*math.acos(-1)*n)/2+n*(math.log(n)-1))/math.log(10))+1
	ans = int(ans)
	
	x = 5
	a2 = 0
	while x <= n:
		a2 = a2 + int(n/x)
		x *= 5
	print ans-a2