#include<fstream>
#include<algorithm>
#define LL long long
#define NMAX 1000005
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");

int t;
int k, n, x[NMAX],s[NMAX], p[NMAX], 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()
{
    f>>t;
    eratostene();

	while(t--)
	{
	    f>>a>>b;
		sum=a;
		n = 0;
		int i = 1;
		while(b > 1)
		{
			if(!(b % ciur[i]))
			{
				p[++n] = ciur[i];
				while(!(b % ciur[i])) b /= ciur[i];
			}
			i++;
		}
		if(b > 1  && (p[i - 1] * p[i - 1]> b))
			p[++n] = b;
		back();
		g<<sum<<'\n';
	}
    g.close();

	return 0;
}