#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cassert>
using namespace std;

#define PRO "pinex"
void OpenFiles(int EVAL)
{
	if(EVAL)
	{
		char input[100] = PRO, output[100] = PRO;
		freopen(strcat(input, ".in"),"r",stdin);
		freopen(strcat(output,".out"),"w",stdout);
	} else
	{
		freopen("test.in","r",stdin);
		//freopen("test.out","w",stdout);
	}
}

#define MAX  1000001
#define INF 0xffffff

unsigned char p[MAX/8+1];
int nr,pr[80000],k,f[20],x[20];

void Ciur()
{
    int i=2;
    while(i<=1000)
    {
        while(p[i/8]&(1<<(i%8)))i++;
        for(int j=i*i;j<MAX;j+=i)p[j/8]|=1<<(j%8);
        i++;
    }
    for(int i=2;i<MAX;i++)
        if(!(p[i/8]&(1<<(i%8))))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)
		{
			f[++k]=pr[i];
			while(a%pr[i]==0)a /= pr[i];
		}
		i++;
	}
	if(a != 1)f[++k] = a;
	//for(int i=1;i<=k;i++)printf("%d ",f[i]);
}

void pinex(long long a)
{
	long long s,r=0;
	int bit,i;
	for(int i=1;i<=k+1;i++) x[i] = 0;
	x[1] = 1; s = f[1]; bit = 1;
	while(x[k+1] == 0)
	{
		if(bit%2)r += a/s; else r -= a/s;
		i=1;
			while(x[i])
			{
				x[i]=0;
				bit--;
				s/=f[i];
				i++;
			}
			x[i]=1;
			bit++;
			s*=f[i];
	}
	printf("%lld\n",a-r);
}

int main(int argv,char *args[])
{
	OpenFiles(argv==0);
	// start
	int n;
	long long a,b;
		Ciur();
		scanf("%d",&n);
		while(n--)
		{
			scanf("%lld %lld",&a,&b);
			desc(b);
			pinex(a);
		}

	return 0;
}