#include <stdio.h>
#include <string.h>
#define ll long long
#define NMAX 21
int m,r,viz[NMAX],nr;
ll x,y,div[NMAX],rez;
void read()
{
	scanf("%lld",&x);
	scanf("%lld",&y);
}
void get_divs()
{
	ll i;
	for (i=2; i*i<=y; i++)
		if (y%i==0)
		{
			div[++r]=i;
			while (y%i==0)
				y/=i;
		}
	if (y!=1)
		div[++r]=y;
}
void update(int k)
{
	if (k & 1)
		rez+=x/nr;
	else
		rez-=x/nr;
}
void back(int k)
{
	if (k==r+1)
		return ;
	int i;
	for (i=viz[k-1]+1; i<=r; i++)
	{
		viz[k]=i;
		nr*=div[i];
		update(k);
		back(k+1);
		nr/=div[i];
	}
}
int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	scanf("%d",&m);
	while (m)
	{
		r=0; nr=1; rez=0;
		memset(viz,0,sizeof(viz));
		read();
		get_divs();
		back(1);
		m--;
		printf("%lld\n",x-rez);
	}
	return 0;
}