#include <fstream>
#include <vector>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int M;
int Prime[1000005],ind;
bool OK[1000005];
long long P[1000005],Sol,A,B;
int X[1000005];
vector <int> Div;
void Eratostene()
{
    int i,j;
    for(i=2;i<=1000000;i++)
    {
       if(OK[i]==0)
       {
           Prime[++ind]=i;
           for(j=i+i;j<=1000000;j+=i)
              OK[j]=1;
       }

    }
}
void Divs()
{
    int i=1;
    while(Prime[i]*Prime[i]<=B && Prime[i]!=0)
    {
        if(Prime[i]!=0 && B%Prime[i]==0)
            Div.push_back(Prime[i]);
        while(B%Prime[i]==0 && Prime[i]!=0)
            B/=Prime[i];
        ++i;
    }
    if(B!=1 && B!=0)
        Div.push_back(B);
}
void Back(int k)
{
    for(int i=X[k-1]+1;i<Div.size();i++)
    {
        X[k]=i;
        P[k]=P[k-1]*Div[X[k]];
        if(k%2==0)
            Sol-=A/P[k];
        else
            Sol+=A/P[k];
        if(k<Div.size())
            Back(k+1);
    }
}
int main()
{
    f>>M;
    P[0]=1;
    X[0]=-1;
    Eratostene();
    while(M--)
    {
        f>>A>>B;
        Div.clear();
        Sol=0;
        Divs();
        Back(1);
        g<<A-Sol<<"\n";
    }
    return 0;
}