给出a,b,c,d,k,求出a<=x<=b, c<=y<=d 且gcd(x,y) == k 的（x,y）的对数。

 

Input

样例个数T (T <= 3000) 每个样例输入a,b,c,d,k，保证所有的a和c都等于1.

(a==1 , c==1 , 0 < b,d <= 100,000 , 0 <= k <= 100,000) 

 

Output

对于每个样例，输出其对应的答案。 

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

Case 1: 9
Case 2: 736427

Hint

样例一 (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

 

做法：求gcd（x,y）==k的对数，化简为 gcd（x/k,y/k）==1，就是在区间  [1,b/k]

和 区间 [1,d/k] 找互质的数，（注意 （a,b）和（b,a）是 同一对） ，我们可以枚举

[1,b/k] 里的数 i，在[1,d/k]区间里找比 i 且与 i 互质的数。

 

互质的对数=总数 - 不互质的数 ，我们可以求不互质的数，将 i 分解为素因子的和，然后用容斥定理求区间不互质的对数。注意 k=0，k>b/k，k>d/k的情况输出0。

 

代码：

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const int maxn=99999999;

vector<ll>q[100005];

void prime()
{
    bool vis[100005];
    memset(vis,0,sizeof(vis));
    vis[1]=vis[0]=1;
    for(ll i=2; i<=100000; i++)
    {
        if(!vis[i])
        {
            for(ll j=i; j<=100000; j+=i)
            {
                q[j].push_back(i);
                vis[j]=1;
            }
        }
    }
}
int main()
{
    prime();
    int t;
    scanf("%d",&t);
    for(int u=1; u<=t; u++)
    {
        ll a,b,c,d,k;
        scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&k);
        printf("Case %d: ",u);
        if(k==0||k>b||k>d)      ///特判
            printf("0\n");
        else
        {
            b=b/k,d=d/k;
            if(b>d)
                swap(b,d);
            ll ans=d;       /// i=1时与每个数都互质。
            for(int i=2; i<=b; i++)
            {
                ll up=(1<<q[i].size())-1,s=0;
                for(ll j=1; j<=up; j++)
                {
                    ll m=1,num=0;
                    for(ll k=0; k<=8; k++)
                    {
                        if(j>>k&1)
                        {
                            m=m*q[i][k];
                            num++;
                        }
                    }
                    if(num&1)
                        s=s+d/m-i/m;
                    else
                        s=s-d/m+i/m;
                }
                ans=ans+d-i-s;
            }
            printf("%lld\n",ans);
        }
    }
}