5146: Trailing Zeroes
[Creator : ]
Description
Find the number of trailing zeroes for the following
function:
$nC_{r}\ast p^{q}$
wheren, r, p, q are given.
For example, if $n = 10, r = 4, p = 1, q = 1$, then the number is 210 so, number of trailing zeroes is 1.
$nC_{r}\ast p^{q}$
wheren, r, p, q are given.
For example, if $n = 10, r = 4, p = 1, q = 1$, then the number is 210 so, number of trailing zeroes is 1.
Input
Input starts with an integer T ($T ≤ 10000$),
denoting the number of test cases.
Each case contains four integers: n, r, p, q ($1 ≤ n, r, p, q ≤10^{6}, r ≤ n$).
Each case contains four integers: n, r, p, q ($1 ≤ n, r, p, q ≤10^{6}, r ≤ n$).
Output
For each test case, print the case number and the number of
trailing zeroes.
Sample 1 Input
2
10 4 1 1
100 5 40 5
Sample 1 Output
Case 1: 1
Case 2: 6