Description

This a veryyyyyyyyyyyyyy hard problem.

One day, Lulichuan was played in city $X$ with his friend, they like to play a game called hide and seek,they was playing hide-and-seek, and suddenly a gust of wind blew up. The wind rolled up all the dust, so they went into a house to take refuge and stayed in the house so boring that they turned around. At the time, a small partner discovered a strange house. His surroundings were gleaming. At this time they cautiously walked into this shimmering room. They found an ancient cheat in the room. With ancient books, if anyone can solve for the number of zeros at the end of a number’ factorial .who will get a mysterious treasure, they soon find out the answer, but they are afraid of making mistakes, so they hope you can count them again. In order to help them test the answer.

Format

Input

The first line $T(0 \lt T \lt 1000)$

Follow $T$ line every line a $N(0 < N < 1000000)$

Output

Answer

Samples

2
5
6

1
1