#include <stdio.h>
#include <math.h>

long long id,i,j,M,A,B,R;
bool pr[500005];
int pr2[500005],fact[1000],nrpr,nrf;


void ciur()
{
	pr2[0]=2; nrpr=0; // pr[i]= daca 2*i+1 e prim
	for(i=1;i<=500000;i++) // pr2[i]=al (i+1)-lea nr prim
	{
		if(!pr[i])
		{
			pr2[++nrpr]=2*i+1;
			for(j=2*i*i+2*i;j<=500000;j+=2*i+1)
				pr[j]=true;
		}
	}
}

void factori()
{
	i=-1; double L=sqrt(B); nrf=0;
	while(B>1)  // descompun B in factori primi
	{           // fact[i]=al i-lea factor prim in descompunerea lui B
		i++;    // nrf = numarul factorilor
		if(B%pr2[i]==0)
		{
			fact[++nrf]=pr2[i];
			while(B%pr2[i]==0)
				B/=pr2[i];
		}
		if(B>1 && pr2[i]>L) // daca gasesc divizor mai mare ca sqrt(B)
		{                   // ma opresc pentru ca e ultimul
			fact[++nrf]=B;
			B=1;
		}
	}
}

void rez()
{
	int nrs=(1<<nrf)-1, nr; // nrs = numarul de ?combinari? intre factori = 2^nrf-1
							//     = numarul de intersectii (submultimi)
	long long prod;         // prod= produsul factorilor luati in considerare
	for(i=1;i<=(long long)nrs;i++)              // in momentul respectiv
	{
		prod=1; nr=0;  // nr = numarul de multimi Ai intersectate
							  // in momentul respectiv
		for(j=0;j<nrf;j++)
			if(i&(1<<j)) // daca i are bitul j = 1
				// Adica, de ex:
				// Cand i ia valorile 2^j(0<=j<nrf) atunci are un singur bit
				// egal cu 1, deci se vor lua submultimile de cate un element.
				// Submultimea a 2^i-a va fi formata din { fact[nrf-i] }
				// Apoi sunt luate submultimile 2^i+1<2^(i+1), apoi 2^i+2<2^(i+1) etc.
				// Ultima submultime e 2^nrf-1 care are toti bitii 1 si, deci, contine
				// toti factorii.
				// Submultimile nu se calculeaza in ordinea numarului de elemente.
			{
				prod=prod*(long long)fact[nrf-j];
				nr++;
			}
		if(nr&1) // <=> nr%2 <=> daca nr e impar
			R+=(long long)A/prod; // (-1)^(nr-1) = +1
		else
			R-=(long long)A/prod; // (-1)^(nr-1)= -1
	} 
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	ciur();
	scanf("%lld",&M);
	for(id=1;id<=M;id++)
	{
		scanf("%lld %lld",&A,&B);
		R=0;
		factori();
		rez();
		printf("%lld\n",(long long)A-R);
	}
	
	
}