#include<cstdio>
#define LL long long
#define NMAX 10000000
using namespace std;
int t;
int k, n, x[NMAX],s[NMAX], p[NMAX];
LL a,b,sum;

inline void prelsol()
{
	if(s[n])
	{
	int pb = 1;
	for(int i = 1; i <= n; ++i)
		if(x[i]) pb *= p[i];
	if(s[n] % 2)
		sum = sum - a / pb;
	else
		sum = sum + a/pb;
	}
}

void back()
{
	k = 1; x[k]= -1;
	do
	{
		while(x[k] < 1)
		{
			x[k]++; s[k] = s[k -1] + x[k];
			if(k == n) prelsol();
			else x[++k] = -1;
		}
		k--;
	}
	while(k);
}
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out","w", stdout);
    scanf("%d", &t);

	while(t--)
	{
	    scanf("%d%d",&a , &b);
		sum=a;
		n = 0;
		int d = 2;
		while(d * d <= b)
		{
			if(!(b % d))
			{
				p[++n] = d;
				while(!(b % d)) b /= d;
			}
			d++;
		}
		if(b > 1)
			p[++n] = b;
		back();
		printf("%d\n",sum);
	}

	return 0;
}