#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=0, 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();
}
}