#include<iostream>
#include<fstream>
#include<math.h>
#include<limits.h>
#include<bitset>
#include<stdio.h>
using namespace std;
long long p[80000];
bitset<1000005> e;
int c;
void erat()
{
    p[0]=2;
    int j,i;
    c=1;
    for(i=3;i<1000005;i=i+2)
    {
        if(e[i]==0)
        {
            p[c]=i;
            ++c;
            for(j=3;i*j<1000005;j=j+2)
                e[i*j]=1;
        }
    }
}
long long sol,prod;
long long d[80000];
int x[80000];
void backt(long long a,int n,int k,long long s)
{
    if(k-1>0)
        sol+=s*(a/prod);
    if(k>n)
        return;
    for(int i=x[k-1];i<n;++i)
    {
        x[k]=i+1;
        prod*=d[i];
        backt(a,n,k+1,-s);
        prod/=d[i];
    }
}
int main()
{
    ifstream si;
    si.open("pinex.in");
    FILE*so=fopen("pinex.out","w");
    int m;
    si>>m;
    int i,j;
    erat();
    long long a,b;
    for(j=0;j<m;++j)
    {
        si>>a>>b;
        long long q=sqrt(b);
        int n=0;

        for(i=0;i<c&&p[i]<=q&&p[i]<=a;++i)
        {
            if(b%p[i]==0)
               d[n++]=p[i];
            while(b%p[i]==0)
                b=b/p[i];
        }
        if(b!=1)
            d[n++]=b;

        prod=1;

        sol=0;

        backt(a,n,1,-1);
        fprintf(so,"%lli\n",a-sol);
        //for(i=0;i<n;++i)
          //  cout<<d[i]<<' ';
        //cout<<endl;
    }
}