#include <bits/stdc++.h>

using namespace std;
const int MAXP=1000000;

int M;
long long int A,B;

bool v[MAXP+1];
vector <int> prim;
vector <long long> p;

ifstream f("pinex.in");
ofstream g("pinex.out");

void generareNumerePrime(int n)
{
    int i,j;
    for(i=3;i*i<=n;i+=2)
    {
        if(v[i]==0)
            for(j=i*i;j<=n;j+=2*i)
                v[j]=1;
    }
    prim.push_back(2);
    for(i=3;i<=n;i+=2)
    {
        if(v[i]==0)
            prim.push_back(i);
    }
}

void generareDivizoriB()
{
    p.clear();
    for(int i=0;1LL*prim[i]*prim[i]<=B;i++)
        if(B%prim[i]==0)
    {
        p.push_back(prim[i]);
        do
            B/=prim[i];
        while(B%prim[i]==0);
    }
    if(B>1)
        p.push_back(B);
}

void calcSol()
{
    int nt=1<<p.size();
    long long int card=0,prod,t;
    for(int i=1;i<nt;i++)
    {
        prod=1;
        int j=0,p2,ndiv=0;
        while((p2=1<<j)<=i)
        {
            if(p2&i)
            {
                prod*=p[j];
                ndiv++;
            }
            j++;
        }
        t=A/prod;
        if(ndiv%2==0)
            card-=t;
        else
            card+=t;
    }
    g<<A-card<<'\n';
}

int main()
{
    generareNumerePrime(MAXP);
    f>>M;
    while(M--)
    {
        f>>A>>B;
        generareDivizoriB();
        calcSol();
    }
    f.close();
    g.close();
    return 0;
}