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

int t;
int n, p[1000], ciur[NMAX], lng_ciur;
LL a,b,sum;
bool 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 back()
{
    LL nr, pb;
    for(int i = 1; i < (1<<n); ++i)
    {
        nr = 0, pb =1;
        for(int j = 0; j < n; ++j)
            if((1<<j) & i) pb *= p[j + 1], nr++;
        if(nr % 2)
            sum = sum - a / pb;
        else
            sum = sum + a/pb;
    }
}
int main()
{
    f>>t;
    eratostene();

	while(t--)
	{
	    f>>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();
		g<<sum<<'\n';
	}
    g.close();

	return 0;
}