FGD正在破解一段密码，他需要回答很多类似的问题：对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a
，y<=b，并且gcd(x,y)=d。作为FGD的同学，FGD希望得到你的帮助。

第一行包含一个正整数n，表示一共有n组询问。（1<=n<= 50000）接下来n行，每行表示一个询问，每行三个
正整数，分别为a,b,d。（1<=d<=a,b<=50000）

对于每组询问，输出到输出文件zap.out一个正整数，表示满足条件的整数对数。

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 50010

#define LL long long

int n;

int prime[maxn], cnt, u[maxn], sum[maxn];

bool vis[maxn];

void u_table() {

	int N = maxn - 10;

	u[1] = 1;

	for(int i = 2; i <= N; i++) {

		if(!vis[i]) prime[++cnt] = i, u[i] = -1;

		for(int j = 1; j <= cnt && (LL)prime[j] * (LL)i <= (LL)N; j++)

			if(i % prime[j]) vis[i*prime[j]] = 1, u[i*prime[j]] = -u[i];

			else{ vis[i*prime[j]] = 1, u[i*prime[j]] = 0; break; }

	}

	for(int i = 1; i <= N; i++) sum[i] = sum[i-1] + u[i];

	return ;

}

int main() {

	u_table();

	n = read();

	while(n--) {

		int a = read(), b = read(), d = read();

		if(a > b) swap(a, b); a /= d; b /= d;

		int p = 1;

		LL ans = 0;

		for(; p <= a;) {

			int np = p;

			p = min(a / (a / np), b / (b / np));

			ans += (LL)(sum[p] - sum[np-1]) * (LL)(a / np) * (LL)(b / np);

			p++;

//			printf("%d\n", p);

		}

		printf("%lld\n", ans);

	}

	return 0;

}