1. Skip to Menu
  2. Skip to Content
  3. Skip to Footer>

Factorials

Used in the 2005 Baldwin-Wallace College High School Programming Competition. See the problem in its original context here (Problem 1).

Given a non-negative integer \(n\), we define \(n!\) (pronounced "\(n\) factorial") as follows:

\(n! = n * (n – 1) * (n – 2) * … * 2 * 1\)

By convention, 0! is defined to be 1. For this problem, we define \(n\)# to be the number of trailing zeros on \(n!\). Here are a few examples:

  • 5! = 120, and so 5# = 1.
  • 2! = 2, and so 2# = 0.
  • 16! = 20,922,789,888,000, and so 16# = 3.
  • 174! = 6,425,425,663,347,064,733,166,342,506,526,881, 458,348,150,508,160,426,541,851,455,077,080, 468,607,287,618,805,557,105,047,805,861,775, 775,912,692,278,116,502,462,953,528,378,524, 937,389,131,268,196,460,620,409,529,506,610, 362,739,317,326,974,626,432,136,901,748,478, 076,969,280,322,196,922,086,635,340,638,923, 811,068,556,323,532,935,233,826,663,322,108, 954,882,867,200,000,000,000,000,000,000,000, 000,000,000,000,000,000, and so 174# = 41.

It is your task to compute the # function for various input values.

Details of the Input

The first line will contain the number \(m\) of cases to follow, and then each of the following \(m\) lines contain a non-negative integer \(n\) which is no greater than 1000.

Details of the Output

Each line of your output will look like

\(n\):  \(n\)#

for that particular value of \(n\). There should be two (2) spaces between the colon and the value of \(n\)#. The value of \(n\)# is guaranteed to fit within the bounds of a standard integer. We do not, however, make any promises about the size of \(n\)!, so beware...

Sample Input

4
5
2
16
174

Sample Output

5:  1
2:  0
16:  3
174:  41