#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;

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

void initialize_ciur()
{
	for(long long i=0;i<ciur.size();i++)
		ciur[i] = 1;
}


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

int put_element(int i)
{
	if(i>=(int)primeNos.size())
		return 0;
	if(!stack.size())
		return primeNos[0];
		
	if(i >= (int)stack.size())
	{
		for(int j = 0;j<(int)primeNos.size();++j)
			if(primeNos[j] > stack[i-1])
				return primeNos[j];
		return 0;
	}
	
	for(int j = 0;j<(int)primeNos.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)
	{
		//printf("%d:  %d: .... %d ",i,p,stack.size());
		if(i>=(int)stack.size())
			stack.push_back(p);
		else
			stack[i] = p;
		
		add(i);
		if(i<(int)primeNos.size()-1)
		{
			if((int)stack.size()>=i)
				stack[i+1] = stack[i];
			back(i+1);
		}
		p = put_element(i);
	}
}
	
void compute()
{
	//long long a,b;
	count = 0;
	scanf("%llu %llu",&a,&b);
	gen_ciur();
	stack.clear();
	back(0);
	

	printf("%llu\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();
}