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

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

void ciurEratostene()
{
    p.assign(sqrtBMAX/2 +1, 1);   //numerele prime mai mici decat sqrt B
    for(int i=1; (i<<1)+1 <= sqrtBMAX; ++i)
        if(p[i])
        {
            p2.push_back(i*2 +1);
            for(int j=3*i+1; (j<<1) <= sqrtBMAX; j+=(i<<1) + 1)
                p[j]=0;
        }
}

void descFactori()
{
    int iPrim=-1, f;       //al i-lea numar posibil prim din ciur
    double radB=sqrt(B);    //evitam sa recalculam sqrt(B)
    nrFactori = 0;          // numarul factorilor primi din descompunerea lui B
    if(B % 2 == 0){         // 2 e caz special
        fact[++nrFactori] = 2;
        while(B % 2 == 0)
            B /= 2;
    }
    while(B>1)
    {
        iPrim++;
        f=p2[iPrim];
        if(B % f == 0)
        {
            fact[++nrFactori] = f;          //retinem factorul
            while(B % f == 0)               //cat timp factorul are mai are puteri
                B /= f;
        }
        if(B>1 && f > radB)      //ultimul factor prim
        {
            fact[++nrFactori] = B;
            break;
        }

    }
}
void rezolva()
{
    descFactori();
    long long nrInter =( 1 << nrFactori  )-1, Rez=0;        //numarul intersectiilor din formula
    long long produs;
    int nrSubm;                                             //in functie de nrSubm stim daca adunam sau scadem numerele din intersectie
    for(long long i=1; i<=nrInter; 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("%d", &M);
    for(int i=1; i<=M; i++)
    {
        scanf("%lld%lld", &A, &B);
        rezolva();
    }
}