#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#define N 100005
using namespace std;

typedef long long LL;
LL euler[N];
int Min, Max;
int p[N][10];//  二维存的是 N 的质因子
int num[N];  // 记录的是 P二维质因子的个数
// 筛选得到 欧拉函数和 质因子
void init()
{
    int i,j;
    memset(num, 0 , sizeof(num));
    memset(euler , 0 ,sizeof(euler));
    euler[1]=1;
    for( i =2 ; i<N ; i++) // 质数从2开始
    {
        if(!euler[i])  //i是质数
        {
            for(j=i; j<N ;j+=i)
            {
                if(!euler[j])  //初次访问j
                    euler[j]=j;
                euler[j]=euler[j]*(i-1)/i; // 欧拉函数
                p[j][num[j]++] = i; // 记录j质因子：第num[j] 位置的是质因子i
               // printf("p[%d][%d]=%d\n",j,num[j]-1,i);
            }
        }
        euler[i]+=euler[i-1];  // ，题目要求，前i个数的欧拉函数值累加和
    }
}
// 容斥原理 值为q,当前点（质因子的下标号），数深（树根为1），
void dfs(int q ,int now , int count , LL lcm ,LL &sum)  // 计算Min与q不互质的个数
{
    if(count>1)
        lcm=p[q][now]*lcm;
    if(count &1)
        sum+=Min/lcm; 
    else
        sum-=Min/lcm;
    for(int i=now+1 ;i <num[q] ; i++)
        dfs(q,i,count+1,lcm, sum);
}
int main()
{
    int  a,b , k,ans=1,t;
    LL temp;
    cin>>t;
    init();
    while(t--)
    {
        scanf("%d%d%d%d%d",&a,&a,&b,&b,&k);
        if(k==0)
        {
            printf("Case %d: 0\n",ans++);
            continue;
        }

        LL sum_=0;
        Max=a>b?a:b;
        Min=a<b?a:b;
        Max/=k;
        Min/=k;
        sum_=euler[Min];
        for(int i=Min+1 ; i<=Max ; i++)  // 枚举 i
        {
            temp=0;
            for(int j=0; j<num[i] ; j++) // 求Min与i不互质的个数。
                dfs(i,j,1,p[i][j],temp);
            sum_+=Min-temp;  // 求Min 与i 互质的个数
        }

        printf("Case %d: %I64d\n",ans++,sum_);

    }
    return 0;
}