题目描述

全球移动通信系统（GSM）网络中最重要的组成部分是所谓的基站收发信台（Base Transceiver Station，BTS）。这些收发信台形成的区域称为小区（这也是“蜂窝电话”名称的由来），每个手机都会连接到信号最强的BTS（简略来说）。当然，BTS需要定期维护，技术人员需要定期检查其功能。

最近，ACM的技术人员遇到了一个非常有趣的问题。给定一组需要访问的BTS，他们需要找到一条最短路径，访问所有给定的点并返回到公司总部。程序员们花了几个月的时间研究这个问题，但毫无进展。他们无法快速找到解决方案。经过很长时间，其中一位程序员在一篇会议文章中发现了这个问题。不幸的是，他发现这个问题是所谓的“旅行商问题”（Travelling Salesman Problem），非常难以解决。如果有$N$个BTS需要访问，可以按任意顺序访问，共有$N!$种可能性需要检查。表示这个数的函数称为阶乘，可以计算为$1 \times 2 \times 3 \times \cdots \times N$。即使对于相对较小的$N$，这个数也非常大。

程序员们意识到他们无法解决这个问题。但由于他们已经获得了政府的研究资助，他们需要继续研究并至少产生一些结果。于是他们开始研究阶乘函数的性质。

例如，他们定义了函数$Z$。对于任何正整数$N$，$Z(N)$是$N!$的十进制形式末尾的零的个数。他们注意到这个函数永远不会减少。如果有两个数$N_1 < N_2$，那么$Z(N_1) \leq Z(N_2)$。这是因为乘以任何正数都不会“丢失”任何末尾的零，只会不断增加新的零。函数$Z$非常有趣，因此我们需要一个计算机程序来高效地计算它的值。

输入格式

第一行输入一个正整数$T$，表示接下来数字的个数。然后是$T$行，每行包含一个正整数$N$，其中$1 \leq N \leq 1000000000$。

输出格式

对于每个数字$N$，输出一行，包含一个非负整数$Z(N)$。

示例输入

6
3
60
100
1024
23456
8735373

示例输出

0
14
24
253
5861
2183837

题目来源

Central Europe 2000