Draco Malfoy and Hermione Granger have gotten into a "battle of brains". Draco was foolish enough to challenge her to a Arithmancy problem. Septima Vector, Arithmancy teacher at Hogwarts, has agreed to give them both a problem which they should solve overnight.

The problem is as follows :-

Firstly, a function F (from naturals to naturals), which is strictly increasing, is defined as follows:-

F(0) = F(1) = 1

F(x) = x * (x - 1) * F(x - 2) ; x > 1

Now, define another function, Z (from naturals to naturals) as

Z(x) = highest value of n such that 10^n divides x

Draco has realized his folly and has come to you asking for help. You don't like him, but you have accepted the challenge as he has agreed to accept your prowess at the your Muggle stuff if you can help him out with this. He doesn't understand computers, so it's time to show him some Muggle-magic

INPUT FORMAT : Single positive integer on the first line, T (<= 100000), which indicates the number of lines that follow. Each of the next T lines contain a positive integer, N ( <= 1000000000).

OUTPUT FORMAT : For every number N in the input, you are expected to output a single number that is equal to Z(F(N)).