#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 1000005
#define MaxP 20
using namespace std;
  
FILE*IN,*OUT;

int M,Size=1,N=0,Prime[MaxN],Sign[2]={1,-1};
long long A,D[MaxP],B;
bool Sieve[MaxN];
void Get_Sieve()
{
	Prime[Size]=2;
	for(int i=3;i<MaxN;i+=2)
	{
		if(!Sieve[i])
		{
			Prime[++Size]=i;
			for(int j=3*i;j<MaxN;j+=2*i)
				Sieve[i]=true;
		}
	}
}
void Decompose(long long X)
{
	N=0;
	for(int i=1;Prime[i]<=X;i++)
	{
		if(Prime[i]*Prime[i]>X)
		{
			D[++N]=X;
			break;
		}
		if(X%Prime[i]==0)
		{
			D[++N]=Prime[i];
			while(X%Prime[i]==0)
				X/=Prime[i];
		}
	}
}
int main()
{
    IN=fopen("test.in","r");
    OUT=fopen("test.out","w");
	
	Get_Sieve();
	long long Out,Aux;
	fscanf(IN,"%d",&M);
	for(int t=1;t<=M;t++)
	{
		fscanf(IN,"%lld%lld",&A,&B);
		int bits=0;
		Out=A;
		Decompose(B);
		for(int i=1;i<(1<<N);i++)
		{
			bits=0;
			Aux=1;
			for(int j=0;j<N;j++)
				if(i&(1<<j))
					Aux*=D[j+1],bits++;
			Out+=Sign[bits%2]*A/Aux;
		}
		fprintf(OUT,"%lld\n",Out);
	}
    return 0;
}