#include <bits/stdc++.h>
#define MAXDIV 1000000

using namespace std;
ifstream fi("pinex.in");
ofstream fo("pinex.out");
bool CIUR[MAXDIV+5];
int m;
long long a,cardreun;
int b,n;
int X[MAXDIV+5],P[MAXDIV+5],S[25];

void ciur()
{
    for(int i=2; i<=MAXDIV; i++)
        CIUR[i]=1;
    for(int i=2; i*i<=MAXDIV; i++)
        if(CIUR[i])
            for(int j=2; i*j<=MAXDIV; j++)
                CIUR[i*j]=0;
}

void genereaza()
{
    for(int i=2,t=1; i<=MAXDIV; i++)
        if(CIUR[i])
            P[t++]=i;
}

void g(int k)
{
    if(k==n)
    {
        /**for(int i=0; i<k; i++)
            fo<<S[i]<<" ";
        fo<<"\n";*/
        int nrel=0;
        long long produs=1;
        for(int i=0; i<k; i++)
            if(S[i])
                nrel++;
        for(int i=0; i<n; i++)
            if(S[i])
                produs*=P[i+1];
        if(nrel)
        {
            if(nrel%2==0)
                cardreun-=(a/produs);
            else
                cardreun+=(a/produs);
        }
        ///fo<<a/produs<<" "<<cardreun<<"\n";
    }
    else
    {
        for(int i=0; i<=1; i++)
        {
            S[k]=i;
            g(k+1);
        }
    }
}

int main()
{
    fi>>m;
    ciur();
    genereaza();
    while(m--)
    {
        fi>>a>>b;
        n=1;
        cardreun=0;
        for(int i=1; P[i] && P[i]*P[i]<=b; i++)
            if(b%P[i]==0)
            {
                n++;
            }
        n--;
        g(0);
        fo<<a-cardreun<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}