#include<cstdio>
#define LL long long
const int Max=100005;
LL elur[Max];//存放每个数的欧拉函数值
int num[Max];//存放数的素因子个数
int p[Max][20];//存放数的素因子
void init(){//筛选法得到数的素因子及每个数的欧拉函数值
    elur[1]=1;
    for(int i=2;i<Max;i++){
        if(!elur[i]){
            for(int j=i;j<Max;j+=i){
                if(!elur[j])
                    elur[j]=j;
                elur[j]=elur[j]*(i-1)/i;
                p[j][num[j]++]=i;
            }
        }
        elur[i]+=elur[i-1]; //进行累加
    }
}
int nop(int n,int now,int t){
    int i;
    int ans=0;
    for(i=t;i<num[now];i++)
        ans+=n/p[now][i]-nop(n/p[now][i],now,i+1);
    return ans;
}
int main(){
    int t,T,a,b,c,d,k,i,j;
    init();
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0){
            printf("Case %d: 0\n",t);
            continue;
        }
        b/=k,d/=k;
        if(b>d){a=b;b=d;d=a;}
        LL ans=elur[b];
        for(i=b+1;i<=d;i++){
            ans+=b-nop(b,i,0);
        }
        printf("Case %d: %lld\n",t,ans);
    }
    return 0;
}