#include <stdio.h>
#include <string.h>
#define ll long long
#define NMAX 21
#define VAL 1000000
int m,r,viz[NMAX],pr[VAL],t;
ll x,y,div[NMAX],rez,nr;
char c[VAL+1];
void read()
{
	scanf("%lld",&x);
	scanf("%lld",&y);
}
void ciur()
{
	int i,j;
	for (i=2; i*i<=VAL; i++)
		if (c[i]==false)
            for (j=i*i; j<=VAL; j+=i)
				c[j]=true;				
	for (i=2; i<=VAL; i++)
		if (!c[i]) 
			pr[++t]=i;
}
void get_divs()
{
	int i;
	for (i=1; i<=t; i++)
		if (y%pr[i]==0)
		{
			div[++r]=pr[i];
			while (y%pr[i]==0)
				y/=pr[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);
	ciur();
	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;
}