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

vector<bool> p;
vector<int> p2, fact;             //numerelele prime generate
int M;

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(long long B)
{
    vector<int>().swap(fact);   //stergem factorii B-ului anterior

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

    }
}
void rezolva(long long A, long long B)
{
    descFactori(B);

    long long nrInter =( 1 << fact.size() )-1, Rez=0, produs;    //numarul intersectiilor din formula
    int nrSubm, nrFactori = fact.size();                //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-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("%d", &M);
    for(int i=1; i<=M; i++)
    {
        scanf("%lld%lld", &A, &B);
        rezolva(A, B);
    }
}