trailing zeros

#include <bits/stdc++.h>
using namespace std;

typedef int l;
typedef long long ll;

#define ft freopen("input.txt", "r", stdin)
#define loop(a, b) for(int i = a; i < b; i++)

l up2, up5;
l down2, down5;
l s, r, p, q;

/// formula
/// s!/ (r! * (s-r)!)
/// (s*(s-1)*(s-2)*....*(s-r+1))/ r!

void up_count()
{
    up2 = 0, up5 = 0;

    ///counting 2 and 5 in s - (s-r+1)
    l range = s-r;
    for(l i = s; i > range; i--){
        l z = i;
        while(z%2 == 0){
            up2++;
            z/=2;
        }
        while(z%5 == 0){
            up5++;
            z/=5;
        }
    }

    ///counting 2 and 5 in p^q
    l x = 0;
    l y = 0;
    while(p%2 == 0){
        x++;
        p/=2;
    }
    while(p%5 == 0){
        y++;
        p/=5;
    }

    /// (s*(s-1)*(s-2)*....*(s-r+1)) this part and p^q this part will be in upper side
    up2 += (q*x);
    up5 += (q*y);
}

///counting 2 and 5 in r!
void down_count()
{
    down2 = 0, down5 = 0;
    for(l i = 1; pow(2, i) <= r; i++){
        down2 += (r/(pow(2, i)));
    }
    for(l i = 1; pow(5, i) <= r; i++){
        down5 += (r/(pow(5, i)));
    }
}

int main()
{
    l n;
    cin >> n;
    loop(0, n){
        cin >> s >> r >> p >> q;
        up_count();
        down_count();
        printf("Case %d: %d\n", i+1, min((up2-down2), (up5-down5)));
    }
    return 0;
}