#include <iostream>
#include <fstream>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
long long a,b,m,scad,temp=1,p[1005],it,b1;
int ind=0,auxx,prim[10005],cont;
bool ok[100005];
void bacK(int k)
{
    if(k==it+1)
    {
        if(!cont)return;
        if(cont%2==1) scad+=(a/temp);
        else scad-=(a/temp);
        return;
    }
    for(int i=0;i<=1;++i)
    {
        if(i)cont++,temp*=p[k];
        bacK(k+1);
        if(i)
        {
            temp/=p[k];
            cont--;
        }
    }
}
void prime()
{
    prim[++ind]=2;
    for(int i=3;i*i<=100000;i+=2)
    {
        if(!ok[i])
        {
            prim[++ind]=i;
            auxx=i*2;
            for(int j=i*i;j<=100000;j+=auxx)
            {
                ok[j]=1;
            }
        }
    }
    for(int i=prim[ind]+2;i<=100000;i+=2)
    {
        if(!ok[i])prim[++ind]=i;
    }
}
int main()
{
    in>>m;
    prime();
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        b1=b;
        --a;
        it=0;
        scad=0;
        for(int j=1;j<=ind;j++)
        {
            if(b%prim[j]==0)
            {
                while(b%prim[j]==0)
                {
                    b/=prim[j];
                }
                p[++it]=prim[j];
            }
        }
        if(b>1)p[++it]=b;
        bacK(1);
        if(b1>1)
        out<<a-scad<<'\n';
        else out<<0<<'\n';
    }
    return 0;
}