#include <fstream>
#include <bitset>
using namespace std;
const int nmax=1000000;
bitset <nmax> v;
int p[79000], x[150],c[150];
ifstream fin("pinex.in");
ofstream fout("pinex.out");
inline void ciur()
{
    int i,j;
    p[++p[0]]=2;
    for(i=3;i*i<=nmax;i+=2)
    {
        if(!v[i]) for(j=i*i;j<=nmax;j+=i) v[j]=1;
    }
    for(i=3;i<=nmax;i+=2) if(!v[i]) p[++p[0]]=i;
}
inline void factorizare(int b,int &k)
{
    int i,div;
    for(i=1;p[i]*p[i]<=b&&i<=p[0];i++)
    {   div=0;
        while(b%p[i]==0) div++,b/=p[i];
        if(div>0) x[++k]=p[i];
    }
    if(b>1) x[++k]=b;
}
inline long long prelucrare(int i,int a)
{
    long long sol=1;
    int j;
    for(j=1;j<=i;j++) sol*=x[c[j]];
    return a/sol;
}
inline void gencomb(int j,int i,int k,long long &sol1,int a)
{
    if(j-1!=i)
    {
        for(int r=c[j-1]+1;r<=k-i+j;r++)
        {
            c[j]=r;
            gencomb(j+1,i,k,sol1,a);
        }
    }
    else sol1+=prelucrare(i,a);
}
inline long long combinare(int k,int a)
{
    int i,semn;
    long long sol=0,sol1;
    for(i=1;i<=k;i++)
    {   sol1=0;
        if((i&1)==0) semn=-1;
        else semn=1;
        gencomb(1,i,k,sol1,a);
        sol+=semn*sol1;
    }
    return sol;
}
int main()
{
    int t,i,k;
    long long a,b;
    fin>>t;
    ciur();
    for(i=0;i<t;i++)
    {
        fin>>a>>b;
        k=0;
        factorizare(b,k);
        fout<<a-combinare(k,a)<<"\n";
    }
}