#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
#include <set>
using namespace std;
#define Max 9973

unsigned char p[250001];
int pr[80000],nr,f[25],k,x[25];

void ciur()
{
	int i=2;
	while(i<=1000)
	{
		while(p[i/8]&(1<<(i%8)))i++;
		for(int j=i*i;j<=1000000;j+=i)p[j/8]|=(1<<(j%8));
		i++;
	}

	for(int i=2;i<=1000000;i++)
		if(!(p[i/8]&(1<<(i%8))))
		{
			nr++;
			pr[nr]=i;
		}
}

void desc(long long a)
{
	int i=1;
	k=0;
	while(i<=nr && pr[i]*pr[i]<=a)
	{
		if(a%pr[i]==0)
		{
			while(a%pr[i]==0)a/=pr[i];
			f[++k]=pr[i];
		}
		i++;
	}
	if(a!=1)
	{
		f[++k]=a;
	}
}

void comb(long long a)
{
	long long s=0,b;
	int i,nr=0;
		memset(x,0,sizeof(x));
	x[1]=1;nr=1;b=f[1];
	while(x[k+1]==0)
	{
		if(nr%2==1)s+=a/b; else s-=a/b;
		i=1; while(x[i]==1)
		{
			nr--;
			x[i]=0;
			b/=f[i];
			i++;
		}
			nr++;
			x[i]=1;
			b*=f[i];
	}
	printf("%lld\n",a-s);
}

int main()
{
	int n;
	long long a,b;
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
		scanf("%d",&n);
		ciur();
		while(n--)
		{
			scanf("%lld %lld",&a,&b);
			desc(b);
			//for(int i=1;i<=k;i++)printf("%d ",f[i]); printf("\n");
			comb(a);
		}
	return 0;
}