#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

#define ull unsigned long long

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int M=1000005;
const int prm=80005;

ull n,a,b,i,m,j,vf,sq,sgn,q,t,g,cnt;
ull st[30],pr[prm],sum,rez;
bool ok,x[prm],p[M];

ull solve(ull k)
{
    for(int q=0;q<=1;++q)
    {
        x[k]=q;
        if(k==vf)
        {
            rez=1ull;
            cnt=0;
            for(int g=1;g<=k;++g)
                if(x[g])
                {
                    rez*=st[g];
                    cnt++;
                }
            if(cnt%2==1)
                sgn=1;
            else
                sgn=-1;
            if(cnt)
                sum-=sgn*(a/rez);
        }
        else
            solve(k+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n;
    for(i=2;i<=M;i++)
        if(!p[i])
        {
            pr[++m]=i;
            for(j=2*i;j<=M;j+=i)
                p[j]=1;
        }
    for(;n;--n)
    {
        fin >> a >> b;
        vf=0;
        sum=a;
        sq=sqrt(b);
        i=1;
        while(pr[i]<=b)
        {
            if(b%pr[i]==0)
            {
                st[++vf]=pr[i];
                while(b%pr[i]==0)
                    b/=pr[i];
            }
            i++;
        }
        if(b>1)
            st[++vf]=b;
//        for(i=1;i<=vf;i++)
//            fout << st[i] << " ";
        solve(1);
        fout << sum << '\n';
    }
    return 0;
}