1 /************************************************************** 2     Problem: 2301 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:10604 ms 7     Memory:1244 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef long long ll;16 const int N = 50005;17 int T;18 int u[N], p[N], tot;19 bool v[N];20  21 inline int read(){22     int x = 0;23     char ch = getchar();24     while (ch < ‘0‘ || ch > ‘9‘)25         ch = getchar();26          27     while (ch >= ‘0‘ && ch <= ‘9‘){28         x = x * 10 + ch - ‘0‘;29         ch = getchar();30     }31     return x;32 }33  34 void pre_work(){35     u[1] = 1;36     int i, j, K;37     for (i = 2; i < N; ++i){38         if (!v[i])39             p[++tot] = i, u[i] = -1;40         for (j = 1; i * p[j] < N && j <= tot; ++j){41             v[K = i * p[j]] = 1;42             if (i % p[j] == 0){43                 u[K] = 0; 44                 break;45             }else u[K] = -u[i];46         }47     }48     for (i = 2; i < N; ++i)49         u[i] += u[i - 1];50 }51  52 ll work(int n, int m, int k){53     n /= k, m /= k;54     if (n > m) swap(n, m);55     ll res = 0;56     int i, last;57     for (i = 1; i <= n; i = last + 1){58         last = min(n / (n / i), m / (m / i));59         res += (ll) (u[last] - u[i - 1]) * (n / i) * (m / i);60     }61     return res;62 }63  64 int main(){65     T = read();66     pre_work();67     int a, b, c, d, k;68     ll ans;69     while (T--){70         a = read(), b = read(), c = read(), d = read(), k = read();71         ans = work(b, d, k) - work(a - 1, d, k) - work(b, c - 1, k) + work(a - 1, c - 1, k);72         printf("%lld\n", ans);73     }74     return 0;75 }