Description
對于給出的n個詢問，每次求有多少個數(shù)對(x,y)，滿足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函數(shù)為x和y的最大公約數(shù)。
Input Format
第一行一個整數(shù)，接下來行每行五個整數(shù)，分別表示

Output Format
共行，每行一個整數(shù)表示滿足要求的數(shù)對的個數(shù)

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

Constraints
對于%的數(shù)據(jù)，滿足。

CCYOS
關(guān)鍵是一個容斥。
設(shè)表示有多少正整數(shù)對，滿足，并且。(題中已給出)
經(jīng)過以下推導(dǎo)：

這是基礎(chǔ)

這是ANS(b,d) - ANS(b,c - 1)，記作O

這是ANS(a - 1,d) - ANS(a - 1,c - 1)，記作C

O - C得到所求

#include<bits/stdc++.h>
using namespace std;

#define mxn 60005
int T,a,b,c,d,k,cnt;
int mu[mxn],vis[mxn],prime[mxn],sum[mxn];

inline int read(){
    char c = getchar();
    int fl = 1,ret = 0;
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void get_mu(int n){
    mu[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i])prime[++cnt] = i,mu[i] = -1;
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i * prime[j]] = 1;
            if(!(i%prime[j]))break;
            else mu[i*prime[j]] = -mu[i];
        }
    }
    for(int i = 1;i <= n;++i)sum[i] = sum[i - 1] + mu[i];
}

inline long long ANS(int N,int M){
    int limit = min(M,N);
    long long ret = 0;
    for(int l = 1,r;l <= limit;l = r + 1){
        r = min(N/(N/l),M/(M/l));
        ret += 1ll * (N/(l*k)) * (M/(l*k)) * (sum[r] - sum[l - 1]);
    }
    return ret;
}

int main(){
    //freopen("P3455.in","r",stdin);
//  freopen("P3345.out","w",stdout);
    T = read();
    get_mu(50000);
    for(int t = 1;t <= T;++t){
        a = read();b = read();c = read();d = read();k = read();
        long long ans = 0;
        ans += ANS(b,d) + ANS(a - 1,c - 1);
        ans =ans - ANS(a - 1,d) - ANS(b,c - 1);
        printf("%lld\n",ans);
    }
    return 0;
}