Poltu and Trailing Zero

Poltu gives a problem to his friend Boltu. The description is given below:

You are given an integer N. You have to calculate the number of trailing zero of $1! × 2! × 3! × 4! × 5! ×……× (N - 1)! × N!$

Here, $0! = 1$ and $A! = A × (A - 1)!$

If you don't know about trailing zero, see this.

Input

The first line contains an integer $T$ ($1 ≤ T ≤ 10^5$), number of test case. Every Test case contains an integer $N$ ($1 ≤ N ≤ 10^9$).

Output

For each test case, print the case number and the result of this problem.

Sample

Input	Output
3 4 5 10	Case 1: 0 Case 2: 1 Case 3: 7