Shortening codes

Given integer n, print number of final zeros of n! (which is factorial of n).

Input

The first line of the standard input contains one integer t (t<2001) which is the number of test cases.

In each of the next t lines there is number n (0<=n<=10^9).

Output

For each test, print the number of final zeros of n!.

Example

Input:
2
10
1000000
Output:
2
249998

Special thanks to Rafał Spręga for the concept of this task.