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⁹