#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#define X 1000000
using namespace std;

vector<bool> p;             //numerelele prime generate
long long A, B, M, prod, Rez;
int nrp, nrSubm;
vector<int> fact;           //nrp = numarul de numere prime pana la 10^6

void ciurEratostene()
{
    p.assign(X/2 +1, 1);   //numerele prime mai mici decat 10^6
    for(int i=1; (i<<1)+1 <= X; ++i)
        if(p[i])
        {
            nrp++;
            for(int j=3*i+1; (j<<1) <= X; j+=(i<<1) + 1)
                p[j]=0;
        }
}

void descInFactoriPrimi()
{
    int iFactor=0, factor;         //al i-lea factor prim din desc. lui B
    double radB=sqrt(B);    //evitam sa recalculam sqrt(B)
    if(B % 2 == 0)
    {
        fact.push_back(2);
        while(B % 2 == 0)
            B /= 2;
    }
    while(B>1)
    {
        iFactor++;
        if(p[iFactor])
        {
            factor=iFactor*2 + 1;
            if(B % factor == 0)
                {
                    fact.push_back(factor);
                    while(B % factor == 0)
                        B /= factor;
                }
            if(B>1 && factor > radB)      //ultimul factor prim
            {
                fact.push_back(B);
                break;
            }
        }
    }
}

void rezolva()
{
    descInFactoriPrimi();
    long long nrIntersectii =( 1 << (fact.size()) ) -1;
    long long produs;  //nr de intersectii/submultimi
    int nrFactori = fact.size();
    for(long long i=1; i<=nrIntersectii; i++)
    {
        produs=1;   nrSubm=0;       //nr submultimilor intersectate
        for(long long j=0; j<nrFactori; j++)
            if( i & (1<<j) )    //i are bitul j
            {
                produs *= fact[nrFactori-j-1];
                nrSubm++;
            }
        if(nrSubm % 2 ==1)
            Rez += A/produs;
        else
            Rez -= A/produs;
    }
    cout<< A - Rez<<'\n';
}

int main()
{
    freopen("pinex.in", "rt", stdin);
    freopen("pinex.out", "wt", stdout);
    ciurEratostene();
    scanf("%lld", &M);
    for(int i=1; i<=M; i++)
    {
        scanf("%lld%lld", &A, &B);
        rezolva();
    }
}