#include <bits/stdc++.h>

using namespace std;
const int MAXP=1000000;

int M;
long long int A,B,card;
int x[20];

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 bt(int k,long long prod)
{
    long long t1,t2;
    for(int i=x[k-1]+1;i<(int)p.size();i++)
    {
        x[k]=i;
        t1=prod*p[i];
        t2=A/t1;
        if(k%2==0)
            card-=t2;
        else
            card+=t2;
        bt(k+1,t1);
    }
}

int main()
{
    generareNumerePrime(MAXP);
    f>>M;
    while(M--)
    {
        f>>A>>B;
        generareDivizoriB();
        x[0]=-1;
        card=0;
        bt(1,1LL);
        g<<A-card<<'\n';
    }
    f.close();
    g.close();
    return 0;
}