#include<iostream>
#include<fstream>
#include<bitset>
#include<cmath>
using namespace std;
ifstream si("pinex.in");
ofstream so("pinex.out");
#define PMAX 80005
#define RAD 1000005
long long p[PMAX];
bitset<RAD> e;
int c;
void erat()
{
    p[0]=2;
    int j,i,k;
    c=1;
    for(i=3;i<RAD;i=i+2)
    {
        if(e[i]==0)
        {
            p[c]=i;
            ++c;
            k=i*2;
            for(j=i+k;j<RAD;j+=k)
                e[j]=1;
        }
    }
}
long long sol,prod,d[PMAX];
int x[PMAX];
void backt(int n,long long a,int k,int s)
{
    if(k-1>0)
        sol+=s*(a/prod);
    if(k>n)
        return;
    int i;
    for(i=x[k-1];i<n;++i)
    {
        x[k]=i+1;
        prod*=d[i];
        backt(n,a,k+1,-s);
        prod/=d[i];
    }
}
int main()
{
    erat();
    int i;
    int m;
    si>>m;
    long long a,b;
    while(m--)
    {
        si>>a>>b;
        int n=0;
        long long q=(long long)sqrt((double)b);
        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(n,a,1,-1);
        so<<a-sol<<'\n';
    }
}