#include <fstream>
#define DN 1000005

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int n,x[DN],m,d[DN],nr,z[DN],p,r[DN];
long long a,b,t,sol;
int main()
{
    for(int i=2; i<DN; i++)
        if(!x[i])
        {
            n++;
            z[n]=i;
            for(int j=i+i; j<DN; j+=i)
                x[j]=1;
        }
    fin>>m;
    for(int h=1; h<=m; h++)
    {
        fin>>a>>b;
        sol=0;
        p=-1;
        for(int i=1; i<=n&&z[i]<=b; i++)
            if(b%z[i]==0)
            {
                p++;
                r[p]=z[i];
                while(b%z[i]==0)
                    b/=z[i];
            }
        if(b!=1)
        {
            p++;
            r[p]=b;
        }
        p++;
        nr=0;
        for(int i=1; i<(1<<p); i++)
        {
            t=1;
            nr=0;
            for(int j=0; j<p; j++)
                if((1<<j)&i)
                {
                    nr++;
                    t*=r[j];
                }
            if(nr%2==0)
                sol=sol-a/t;
            else
                sol=sol+a/t;
        }
        fout<<a-sol<<'\n';
    }
}