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