#include <iostream>
#include <fstream>
#define nrmax 999999
using namespace std;
typedef long long ll;
ll prim[40];
short v[1000000];
ll divnr,di[200000];
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int main()
{ll a,b,sol,nrd,i,j;
ll nr,d;

for(i=2;i<=nrmax;i++)
    if(!v[i]) {di[++divnr]=i; for(j=2*i;j<=nrmax;j+=i)v[j]=1;}
int m;
fin>>m;
while(m--)
    {fin>>a>>b;
    nr=0;
    for(d=1;di[d]<=b && d<=divnr;d++)
        if(b%di[d]==0)
    {
        prim[++nr]=di[d];
        while(b%di[d]==0)b/=di[d];
    }
    if(b>1)prim[++nr]=b;
    sol=a;

    for(i=1;i<(1ll<<nr);i++)
     {   d=1;nrd=0;
         for(j=0;(1ll<<j)<=i;j++)
            if((1ll<<j) & i)
             {nrd++; d*=prim[j+1];}

            if(nrd%2)nrd=-1;
            else nrd=1;
        sol=sol+1ll*nrd*a/d;
     }

     fout<<sol<<'\n';
}

}