#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define maxn 1000006


ll cnt2(ll n)
{
    ll cnt=0;
   while(n)
        {
            cnt+=(n/2);
            n/=2;
            
        }
    return cnt;
}



ll cnt5(ll n)
{
    ll cnt=0;
        while(n)
        {
            cnt+=(n/5);
            n/=5;
        }
    
    return cnt;
}



ll cntp5(ll n)
{
    ll cnt=0;
    
        while(n%5==0)
        {
            cnt++;
            n/=5;
        }
    return cnt;
}


ll cntp2(ll n)
{
    ll cnt=0;
    
        while(n%2==0)
        {
            cnt++;
            n/=2;
        }
    
    return cnt;
}

int main()
{
  //  sieve();
    ll n,p,q,t,r,cas,a,b,c,d;
    cin>>t;
    for(cas=1;cas<=t;cas++)
    {
        cin>>n>>r>>p>>q;
        //for ncr;
       ll i=cnt2(n);
     //  cout<<"n er 2 count "<<i<<endl;
       ll j=cnt5(n);
     //  cout<<"n er 5 count "<<j<<endl;
       
       ll k=cnt2(r);
    //   cout<<"r er 2 count "<<k<<endl;
       ll l=cnt5(r);
      // cout<<"r er 5 count "<<l<<endl;
       ll m=cnt2(n-r);
      // cout<<"n-r er 2 count "<<m<<endl;
       ll o=cnt5(n-r);
      // cout<<"n-r er 5 count "<<o<<endl;
       
        
        //for p^q
        
       ll px=q*cntp2(p);
     //  cout<<"p er 2 count "<<px<<endl;
       ll py=q*cntp5(p);
      // cout<<"p er 5 count "<<py<<endl;
       ll sum1=(i-k-m+px);
       ll sum2=(j-l-o+py);
     //  cout<<"Sum1 "<<sum1<<" sum2 "<<sum2<<endl;
       ll ans=min(sum1,sum2);
        cout<<"Case "<<cas<<": "<<ans<<endl;
    }
    return 0;
}