#include<stdio.h>
#include<fstream>
using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

#define ll long long
#define MaxN 1000100
#define MaxP 100

int M,Prim[MaxN],V[MaxP],PrimV[MaxN];
ll A,B,sol;

void ciur(void)
{
	int N = 1000000;
	for(int i=2;i<=N;i++)
		if(!PrimV[i])
		{
			Prim[++Prim[0]] = i;
			for(int j=i+i;j<=N;j+=i)
				PrimV[j] = 1;
		}
}

void desc(void)
{
	ll x = B,sqrtx = sqrt((double)A);
	V[0] = 0;
	for(int i=1;x != 1 && Prim[i] <= sqrtx;i++)
		if(x % Prim[i] == 0)
		{
			V[++V[0]] = Prim[i];
			while(x%Prim[i] == 0)
				x /= Prim[i];
		}
	if(x != 1)
		V[++V[0]] = x;
}

void back(int k,int p,int nr)
{
	if(k == V[0] + 1)
	{
		if(p != 1)
		if(nr&1)
			sol += A/p;
		else
			sol -= A/p;
		return ;
	}
	back(k+1,p,nr);
	back(k+1,p*V[k],nr+1);
}

int main()
{
	f >> M;
	ciur();
	for(int i=1;i<=M;i++)
	{
		f >> A >> B;
		desc(); sol = 0;
		back(1,1,0);
		g << A-sol << "\n";
	}
}