#include <bits/stdc++.h>

using namespace std;

int factori[20];
int marime;

void descomp(long long x)
{
		for(int i=2;i*i<=x;i++)
		{
			if(x%i==0)
			{
				while(x%i==0)
					x/=i;
				factori[marime++]=i;
			}
		}
		if(x>1)
			factori[marime]=x;
}
long long pinex(long long x)
{
	long long s=0;
	long long n=(1<<(marime+1))-1;
	for(long long i=1;i<=n;i++)
	{
		int p=1;
		int siz=0;
		for(int j=0;j<=marime;j++)
		{
			if((i&(1<<j))!=0)
			{
				p*=factori[j];
				siz++;
			}
		}
		if(siz%2==0)
			s-=x/p;
		else
			s+=x/p;
	}
	return s;
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    short m;
    long long a, b;

		scanf("%hd", &m);
		while(m)
		{
				scanf("%lld%lld", &a, &b);
				descomp(b);
				printf("%lld\n", a-pinex(a));
				memset(factori, 0, sizeof(factori));
				marime=0;
				m--;
		}

    return 0;
}