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

vector<bool> p;             //numerelele prime generate
long long A, B, M;
int fact[sqrtBMAX/2 + 5], nrFactori;

void ciurEratostene()
{
    p.assign(sqrtBMAX/2 +1, 1);   //numerele prime mai mici decat 10^6
    for(int i=1; (i<<1)+1 <= sqrtBMAX; ++i)
        if(p[i])
        {
            for(int j=3*i+1; (j<<1) <= sqrtBMAX; 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)
    nrFactori = 0;
    if(B % 2 == 0)
    {
        fact[++nrFactori] = 2;
        while(B % 2 == 0)
            B /= 2;
    }

    while(B>1)
    {
        iFactor++;
        if(p[iFactor])
        {
            factor=iFactor*2 + 1;
            if(B % factor == 0)
                {
                    fact[++nrFactori] = factor;
                    while(B % factor == 0)
                        B /= factor;
                }
            if(B>1 && factor > radB)      //ultimul factor prim
            {
                fact[++nrFactori] = B;
                break;
            }
        }
    }
}
void rezolva()
{
    descInFactoriPrimi();
    long long nrIntersectii =( 1 << nrFactori  )-1, Rez=0;
    long long produs;
    int nrSubm;
    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];
                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();
    }
}