#include <stdio.h>

#define MAX 1000000

long long p[1100000], D[100000];
long long A, B, BC, S, P;
long long n, i, j, np, d;


int main()
{
	FILE *f = fopen ("pinex.in","r");
	FILE *g = fopen ("pinex.out","w");
	fscanf (f,"%lld", &n);
	
	for (i=2; i<=1000; ++i)
		if(!p[i])
		{
			p[++np] = i;
			for (j=i*i; j<=MAX; j+=i)
				p[j] = 1;
		}
	for (i=1001; i<=MAX; ++i)
		if (!p[i])
			p[++np] = i;
	
	D[0] = 1;
	for (;n; n--)
	{
		fscanf (f,"%lld %lld", &A, &B);
		d = 1;
		BC = B;
		for (i=1; i<=np; ++i)
		{
			if (p[i] * p[i] > BC)
				break;
			if (BC % p[i] == 0)
			{
				P = p[i];
				while (BC % P == 0)
					BC /= P;
				P =-P;
				for (j=0; j<d; ++j)
					D[j+d] = P * D[j];
				d *= 2;				
			}
		}
		if (BC > 1)
		{
			P =-BC;
			for (j=0; j<d; ++j)
				D[j+d] = P * D[j];
			d *= 2;
		}	
		S = 0;
		for (i=0; i<d; ++i)
			S += A / D[i];
		fprintf (g,"%lld\n",S);
	}
	
	fclose(g);
	fclose(f);
	return 0;
}