#include<fstream>
#define ll long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
ll a1,b,n,i,nr,fact[50];
int v[100000];
bool a[1000001];
void ciur()
{int i,j,nr;
v[1]=2;
for(i=3;i<=1000;i=i+2)
	if(a[i]==0)
		for(j=i*i;j<=1000001;j=j+i)
			a[j]=1;
nr=1;
for(i=3;i<=1000001;i=i+2)
	if(a[i]==0)
		++nr,v[nr]=i;
}
void desc(ll b)
{
    int d;
    for(d=1;v[d]*v[d]<=b&&b>1;++d)
    if(!(b%v[d]))
    {
        ++nr;
        fact[nr]=v[d];
        while(!(b%v[d]))
        b/=v[d];
    }
    if(b>1)
    ++nr,fact[nr]=b;
}
ll rez()
{
    ll sol=a1,p,t=1<<nr;
    int nr1=0,i,j;
    for(i=1;i<t;++i)
    {
        nr1=0;
        p=1;
        for(j=0;j<nr;++j)
        if(i&(1<<j))
        p=1ll*p*fact[j+1],++nr1;
        if(nr1%2)
        nr1=-1;
        else
        nr1=1;
        sol+=1ll*nr1*a1/p;
    }
    return sol;
}
int main()
{
    f>>n;
    ciur();
    for(i=1;i<=n;++i)
    {
        nr=0;
        f>>a1>>b;
        desc(b);
        g<<rez()<<'\n';
    }
    return 0;
}