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
for _ in xrange(int(raw_input())):
	n = int(raw_input())
	
	#m = int(math.log10((n/math.exp(1.0))**n*math.sqrt(2*math.pi*n)*math.exp(1/12.0/n)))
	m = int(n*math.log10(n/math.e) + 0.5*(math.log10(2*math.pi*n)))
	a = n/5
	z = n//5
	i=2
	while a > 1:
		a = n/(5**i)
		z += n//(5**i)
		i += 1
	print m-z+1