#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 p[M],st[M],pr[prm],sum,rez;
bool ok,x[prm];

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=b/2+1;
        for(i=1;pr[i]<=sq;i++)
            if(b%pr[i]==0)
                st[++vf]=pr[i];
        if(!vf)
            st[++vf]=b;
        solve(1);
        fout << sum << '\n';
    }
    return 0;
}