#include <bits/stdc++.h>
#define NM 1000000
#define Nm 30
#define ull unsigned long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

int n,st[Nm];
ull t,a,b,k,p,sol,v[Nm],dv[78500];
bool viz[Nm],fr[NM];

void Citeste();
void Solve();
void Ciur();
void BKT(int);

int main()
{   Citeste();
    f.close();
    g.close();
    return 0;
}

void Citeste()
{   Ciur();
    f>>t;
    while(t--)
    {   f>>a>>b;
        p=1;
        n=sol=0;
        Solve();
        g<<a-sol<<'\n';
    }
}

void Solve()
{   int d=0;
    while(b>1)
    {   d++;
        if(b%dv[d]==0)
        {   v[++n]=dv[d];
            while(b%dv[d]==0)
                b/=dv[d];
        }
        if(dv[d]*dv[d]>b) break;
    }
    if(b>1)
        v[++n]=b;
    BKT(1);
}

void Ciur()
{   for(int i=2; i<=NM; i++)
        if(!fr[i])
        {   dv[++k]=i;
            for(int j=2; j*i<=NM; j++)
                fr[i*j]=1;
        }
}

void BKT(int vf)
{   for(int i=1; i<=n; i++)
        if(!viz[i])
        {   viz[i]=true;
            st[vf]=i;
            if(st[vf]>st[vf-1])
            {   p*=v[st[vf]];
                (vf%2 ? sol+=a/p : sol-=a/p);
                BKT(vf+1);
                p/=v[st[vf]];
            }
            viz[i]=false;
        }
}