#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m;
long long a,b,mask,produs,ans;
vector<long long>primes;
long long d[101],lg;
bool c[1000006];
int main()
{
    fin>>m;
    c[0]=1;
    c[1]=1;
    for(int i=2;i<=1000000;i++)
        if(c[i]==0)
        {
            primes.push_back(i);
            for(int j=2;j<=1000000/i;j++)
                c[i*j]=1;
        }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        ans=0;
        int div=0;
        lg=0;
        while(b>1)
        {
            int divizor=primes[div];
            if(b%divizor==0)
                d[++lg]=divizor;
            while(b%divizor==0)
                b/=divizor;
            div++;
            if(primes[div]*primes[div]>b&&b>1)
            {
                d[++lg]=b;
                break;
            }
        }
        for(mask=1;mask<(1<<lg);mask++)
        {
            int nr=0;
            produs=1;
            for(int j=0;j<lg;j++)
                if((1<<j)&mask)
                {
                    nr++;
                    produs=produs*1LL*d[j+1];
                }
            long long rez=a/produs;
            if(nr%2==1)
                ans+=rez;
            else
                ans-=rez;
        }
        fout<<a-ans<<'\n';
    }
    return 0;
}