#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;
long long sol,prod,d[PMAX];
int x[PMAX];
void erat()
{
    int i,j,k;
    p[0]=2;
    c=1;
    for(i=3;i<RAD;i+=2)
    {
        if(e[i]==0)
        {
            p[c++]=i;
            k=i*2;
            for(j=i+k;j<RAD;j+=k)
            {
                e[j]=1;
            }
        }
    }
}
void backt(int n,long long a,int k,int s)
{
    if(k!=1)
    {
        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 m;
    int i;
    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&&b!=1;++i)
        {
            if(b%p[i]==0)
            {
                d[n++]=p[i];
                while(b%p[i]==0)
                    b/=p[i];
            }
        }
        if(b!=1)
        {
            d[n++]=b;
        }
        prod=1;
        sol=0;
        backt(n,a,1,-1);
        so<<a-sol<<'\n';
    }
}