/*#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>
#define nmax 1000005
#define ll long long 
using namespace std;
ifstream fin("pinex.in");
ofstream fout ("pinex.out") ; 
ll i, j, n, B, m, k; 
ll A;
bool v[1000002];
int a[7330000] , d[6330000];
void ciur()
{
	int i , j; 
	for( i = 2; i < nmax; i++)
	{
		if( v[i] == 0 )
			for(j = i + i ; j < nmax; j += i  )
				v[j] = 1;
	}
	for( j = 2; j < nmax; j++ )
		if(v[j] == 0 )
		{
			a[++k] = j; 
			
		}
		

}

ll nrdiv()
{
	ll i = 0 , nr = 0, x, ok = 1, ret;
	
	ll sol = 0;
	while ( B > 1)
	{
		i++;
		if(B % a[i] == 0)
		{
			d[++nr] = a[i]; 
			while(B % a[i] == 0)
				B /= a[i]; 

		}
		if( a[i] * a[i] > B && B > 1) 
		{
			d[++nr] = B; 
			B = 1;
		}
		
	}
	for( i = 1; i < (1<<nr) ;i++)
	{
		x = 1;
		ok = 1;
		for(j = 0 ; j <	nr ; j++)
			if( ( 1 << j ) & i)
			{
				x *= d[ j + 1 ] ;
				ok++;
			}
			ret = A / x ;
		if(ok % 2 == 0 )
			sol += ret;
		else
			sol -= ret;
				
	}
	//fout << sol << '\n' ;
	fout << A - sol <<'\n' ;
	return A - sol ;
}

void calc()
{
	int i;
	
	fin >> m ;
	
	for( i = 1; i <= m; i++)
	{
		fin >> A >> B;
		//fout << A <<  " " << B << '\n'; 
		nrdiv();
		
	}		
		
	
}
int main()
{
	ciur();
	calc();
	fin.close();
	fout.close();
	return 0;
}