#include<cstdio>
#define LL long long
#define NMAX 1000009
using namespace std;
int t;
int k, n, x[65],s[65], p[65], ciur[NMAX], lng_ciur;
LL a,b,sum;
char semn[NMAX];

inline void eratostene()
{
    for(int i = 2; i <= NMAX; i += 2)
        semn[i] = 1;
    ciur[1] = 2;
    lng_ciur = 1;
    for(int i = 3; i <= NMAX; i += 2)
    {
        if(!semn[i])
        {
            ciur[++lng_ciur] = i;
            semn[i] = 1;
            for(int j = i + i; j <= NMAX; j += i) semn[j]= 1;
        }
    }
}

inline void prelsol()
{
	if(s[n])
	{
	int pb = 1;
	for(int i = 1; i <= n; ++i)
		if(x[i]) pb *= p[i];
	if(s[n] % 2)
		sum = sum - a / pb;
	else
		sum = sum + a/pb;
	}
}

void back()
{
	k = 1; x[k]= -1;
	do
	{
		while(x[k] < 1)
		{
			x[k]++; s[k] = s[k -1] + x[k];
			if(k == n) prelsol();
			else x[++k] = -1;
		}
		k--;
	}
	while(k);
}
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out","w", stdout);
    scanf("%d", &t);
    eratostene();

	while(t--)
	{
	    scanf("%d%d",&a , &b);
		sum=a;
		n = 0;
		int i = 1;
		while(ciur[i] * ciur[i] <= b)
		{
			if(!(b % ciur[i]))
			{
				p[++n] = ciur[i];
				while(!(b % ciur[i])) b /= ciur[i];
			}
			i++;
		}
		if(b > 1)
			p[++n] = b;
		back();
		printf("%d\n",sum);
	}

	return 0;
}