LOJ_1090 - Trailing Zeroes (II)

/*
@author -> unlucky_13
problem link::
*/

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<list>
#include<sstream>
#include<fstream>
using namespace std;

int catchPfac (int n,int p){
    int cnt = 0 ;
    while(n!=0){
        cnt +=n/p ;
        n =n/p ;
    }

    return cnt ;
}
int catchPnum (int n,int P){
    int cnt = 0 ;
    while(n%P==0){
        cnt ++ ;
        n =n/P ;
    }

    return cnt ;
}

int main() {
    //freopen("C:\\Users\\Mazhar\\Desktop\\eclipse\\in.txt","r",stdin) ;

    int tc,ct = 1,n, r, p,q;
    scanf("%d",&tc) ;
    while(tc--){
        scanf("%d %d %d %d",&n,&r,&p,&q) ;
        int t5 = catchPfac(n,5)-catchPfac(n-r,5)-catchPfac(r,5)+q*catchPnum(p,5) ;
        int t2 = catchPfac(n,2)-catchPfac(n-r,2)-catchPfac(r,2)+q*catchPnum(p,2) ;
        cout<<"Case "<<ct++<<": "<<min(t5,t2)<<endl ;

    }









    return 0;
}