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

int M,Size=1,N=0,Prime[MaxS],Sign[2]={1,-1},D[MaxP];
long long A,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[j]=true;
		}
	}
}
int main()
{
    IN=fopen("pinex.in","r");
    OUT=fopen("pinex.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;
		N=-1;
		for(int i=1;Prime[i]*Prime[i]<=B;i++)
		{
			if(B%Prime[i]==0)
			{
				D[++N]=Prime[i];
				while(B%Prime[i]==0)
					B/=Prime[i];
			}
		}
		if(B>1)
			D[++N]=B;
		int len=1<<(N+1);
		for(int i=1;i<len;i++)
		{
			bits=0;
			Aux=1;
			for(int j=0;j<=N;j++)
				if(i&(1<<j))
					Aux*=D[j],bits++;
			Out+=Sign[bits%2]*A/Aux;
		}
		fprintf(OUT,"%lld\n",Out);
	}
    return 0;
}