#include<vector>
#include<cstdio>
#include<cmath>
using namespace std;

vector<bool> ciur;
vector<int> primeNos;
vector<int> stack;

int count = 0;
long long a,b;
int size;

void mark(int i, long long n)
{
	int j = 2*i;
	stack.push_back(i);
	while(j<=n)
	{
		ciur[j] = 0;
		j += i;
	}
}

void gen_ciur()
{
	
	int i=2;
	long long k = sqrt(b)+1;
	ciur.clear();
	ciur.resize(k+5,1);
	stack.clear();
	
	while(i<=k)
	{
		if(ciur[i])
			mark(i,k);
		++i;
	}
}
void compute_primes()
{
	primeNos.clear();
	long long n = b;
	int i=0,s=stack.size();
	while(n>1&&i<s)
	{
		if(n%stack[i]==0)
		{	
			primeNos.push_back(stack[i]);
			while(n%stack[i]==0)
				n/=stack[i];
		}
		i++;
	}
	if(n>1)
		primeNos.push_back(n);
}

int put_element(int i)
{
	if(i>=size)
		return 0;
	
	for(int j = 0;j<size;++j)
		if(primeNos[j]>stack[i])
			return primeNos[j];
	
	return 0;
}

void add(int n)
{
	long long sum = 1;
	for(int i = 0;i<=n;++i)
	{	
		//printf("%d,",stack[i]);
		sum *= stack[i];
	}
	//printf("\n");
	if(n%2)
		count -= a/sum;
	else
		count += a/sum;
		
	//printf(" -- %llu, %d\n",sum,count);
}

void back(int i)
{
	int p = put_element(i);
	while(p)
	{
		stack[i] = p;
		add(i);
		if(i<size-1)
		{
			stack[i+1]=stack[i];
			back(i+1);
		}
		p = put_element(i);
	}
}
	
void compute()
{
	//long long a,b;
	count = 0;
	scanf("%lld %lld",&a,&b);
	gen_ciur();
	compute_primes();
	stack.clear();
	size=primeNos.size();
	//printf("size::%d\n",size);imeNos[i]);
	stack.resize(size,0);
	stack[0]=0;
	back(0);
	
	printf("%lld\n",a-count);
	

}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		compute();
		
	return 0;
}