#include <fstream>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long t, a, b, k, x, nr, sol, p[1000001], v[101];
bool ciur[1000001];
int main() {
k=0;
for(int i=2; i<=1000000; i++)
{
if(!ciur[i])
{
p[++k]=i;
for(int j=2*i; j<=1000000; j+=i)
{
ciur[j]=true;
}
}
}
cin>>t;
while(t--)
{
cin>>a>>b;
x=b;
k=0;
for(int i=1; p[i]*p[i]<=b && x!=1; i++)
{
if(x%p[i]==0)
{
v[++k]=p[i];
while(x%p[i]==0)
{
x=x/p[i];
 }     
}
}
if(x!=1)
{
v[++k]=x;
}
sol=0;
for(int i=1; i<(1<<k); i++)
{
nr=0;
x=1;
for(int j=0; j<k; j++)
{
if((1<<j)&i)
{
x*=v[j+1];
nr++;
}
}
if(nr%2==1)
{
sol-=a/x;
}
else
{
sol+=a/x;
}
}
if(sol>0)
{
cout<<a-sol<<"\n";
}
else{
cout<<a+sol<<"\n";
}
}
}