/*#include<cstdio>
#define sqrtB 1000000
using namespace std;

char v[sqrtB+5];
long long fp[200005],pr[200005],ka,cont;

void ciur ()
{
    long long i,j;
    for (i=2; i<sqrtB; i++)
        if (!v[i])
        {
            pr[++ka]=i;
            for (j=i+i; j<sqrtB; j+=i)
                v[j]=1;
        }
}

void fact_primi (long long x)
{
    cont=0;
    for (int i=1; pr[i]*pr[i]<=x; i++)
        if (x%pr[i]==0)
        {
            while (x%pr[i]==0)
                x/=pr[i];
            fp[++cont]=pr[i];
        }
    if (x!=1)
        fp[++cont]=x;
}

long long calc (long long x,long long a)
{
    long long sum=a,prod,nr;
    for (int i=1; i<(1<<cont); i++)
    {
        nr=0; prod=1;
        for (int j=0; j<cont; j++)
            if ((1<<j) & i)
            {
                prod=1LL*prod*fp[j+1];
                nr++;
            }
        if (nr%2)
            nr=-1;
        else nr=1;
        sum=sum+1LL*nr*(a/prod);
    }
    return sum;
}

int main ()
{
    int m,i;
    long long a,b;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    ciur();
    scanf("%d",&m);
    for (i=1; i<=m; i++)
    {
        scanf("%lld%lld",&a,&b);
        fact_primi(b);
        printf("%lld\n",calc(b,a));
    }
    return 0;
}
*/

#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
#define dim 1000005
#define ll long long
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bitset <dim> v;
ll prime[dim/10],a,b;
int factor[dim/10], putere[dim/10];

void solve()
{
	int d=0, vf=0;
	while(b>1)
	{
		++d;
		if(b%prime[d]==0)
		{
			factor[++vf]=prime[d];
			while(b%prime[d]==0)
				b/=prime[d];
		}
		if(prime[d]*prime[d]>b && b>1)
		{
			factor[++vf]=b;
			b=1;
		}
	}
	
	ll sol=a;
	
	for(int i=1;i<(1<<vf);++i)
	{
		ll val=0;
		ll prod=1;
		for(int j=0;j<vf;++j)
			if( (1<<j)&i)
			{
				prod=1LL*prod*factor[j+1];
				++val;
			}
	
		if(val%2==1)
			val=-1;
		else
			val=1;
		
		sol=sol+1LL*val*a/prod;
	}
	fout<<sol <<'\n';
}

int main()
{
	int  i, nr=0,t;
	fin>>t;
	
	prime[++nr]=2;
	
	for(i=2;i<dim;++i)
	{
		++i;
		if(v[i]==0)
		{
			prime[++nr]=i;
			for(int j=1;j<dim/i;++j)
			{
				v[j*i]=1;
				++j;
			}
		}
	}
	
	for(;t;--t)
	{
		fin>>a >>b;
		solve();
	}
	
	return 0;
}