Given integer n, print length of n! (which is factorial of n).

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).

Example

Input:
3
1
10
100

Output:
1
7
158