HDU 1695

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef __int64 ll;

vector <int> v;
int b,d,k;

int main(){
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%*d%d%*d%d%d",&b,&d,&k);
        if(!k){
            printf("Case %d: 0\n",cas);
            continue;
        }
        b/=k;d/=k;
        if(b>d)swap(b,d);
        int i;
        ll ans=0; 
        for(i=1;i<=b;i++){
            int temp=i;
            v.clear();
            for(int j=2;j*j<=i;j++){
                if(i%j==0){
                    v.push_back(j);
                    while(i%j==0)i/=j;
                }
            }
            if(i>1)v.push_back(i);
            int m=v.size();
            i=temp;
            ll res=0; 
            for(int j=1;j<(1<<m);j++){
                int cnt=0;
                ll val=1;
                for(int k=0;k<m;k++){
                    if(j&(1<<k)){
                        cnt++;
                        val*=v[k];
                    }
                }
                if(cnt&1)res+=d/val-(i-1)/val;
                else res-=d/val-(i-1)/val;
            }
            ans+=(d-i+1)-res;
        }
        printf("Case %d: %I64d\n",cas,ans);
    }
    return 0;
}