#include<iostream>
#include<fstream>
using namespace std;
int m, st[80000];
long long d[80000], numar, a;

int calculez()
{
    long long p=1;
    int nr=0, i;
    for(i=0;i<m;i++)
    if(st[i]==1){
        nr++;
        p*=d[i];
    }
    p=a/p;
    if(nr%2)
        p*=(-1);
    if(nr!=0)
    return p;
else return 0;
}
void bktr(int q)
{
    long long aux;
    if(q==m){
    {aux=calculez(); }
            numar+=aux;
    }
    else
    {
        st[q]=1;
        bktr(q+1);
        st[q]=0;
        bktr(q+1);
    }

}
int main()
{
    ifstream f("pinex.in");
    ofstream g("pinex.out");
     bool ciur[1000001];
     long long n, y, v[80000], b;
     int i, k, p, r, t, j;
    for(i=2; i<=1000000; i++)
             ciur[i]=true;
    r=1000;
    for(p=2; p<=r; p++){
             if(ciur[p]==1)
             for(j=p*p; j<=1000000; j+=p)
                      ciur[j]=false;
    }
    k=0;
    for(i=2;i<=1000000;i++)
        if(ciur[i]==true)
            v[k++]=i;
    f>>n;
    for(i=0;i<n;i++){
        f>>a>>b;
        t=0;
        m=0;
        y=b;
        numar=0;
        while(v[t]*v[t]<=y && t<k && b>1){
            if(b%v[t]==0 && b){
                while(b%v[t]==0)
                    b/=v[t];
                d[m++]=v[t];
            }
            t++;
        }
        if(b>1)
            d[m++]=b;
        bktr(0);
        g<<a+numar<<"\n";
        }
f.close();
return 0;
    }