#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long n,a,b,k,v[1000003],x,rez,m,u[1000003];
bitset<1000003> c;
int main()
{
    for(int i=2;i<=1000;++i)
    {
        for(int j=2;j<=1000000/i;++j)
        {
            c[i*j]=1;
        }
    }
    c[1]=1;
    f>>m;
    for(int z=1;z<=m;++z)
    {
        f>>a>>b; n=rez=0;
        x=sqrt(b);
        for(int i=2;i<=x;++i)
        {
            if(c[i]==0 && b%i==0)
            {
                ++n;
                v[n]=i;
                if(c[b/i]==0)
                {
                    ++n;
                    v[n]=b/i;
                }
            }
        }
        if(n==0)
        {
            n=1;
            v[n]=b;
        }
        for(int i=1;i<=n;++i)
        {
            k=1;
            u[1]=0;
            while(k>0)
            {
                if(u[k]<n)
                {
                    ++u[k];
                    if(k==i)
                    {
                        x=1;
                        for(int j=1;j<=k;++j)
                        {
                            x*=v[u[j]];
                        }
                        if(i%2==1)
                        {
                            rez+=a/x;
                        }
                        else
                        {
                            rez-=a/x;
                        }
                    }
                    else
                    {
                        ++k;
                        u[k]=u[k-1];
                    }
                }
                else
                {
                    --k;
                }
            }
        }
        g<<a-rez<<'\n';
    }
    return 0;
}