#include<bits/stdc++.h>
#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';
    }
}