#include <bits/stdc++.h>

using namespace std;

long long t,a,b,pr=1,sum=0;

vector <int> p;

bitset <1000005> f;

vector <int> d;

int u[100005];

int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    f[0]=1;
    f[1]=1;
    for(int i=4;i<=1000005;i+=2)
    {
        f[i]=1;
    }
    for(int i=3;i*i<=1000005;i+=2)
    {
        if(f[i]==0)
        {
            for(int j=i;j*i<=1000005;j+=2)
            {
                f[i*j]=1;
            }
        }
    }
    for(int i=1;i<=1000005;++i)
    {
        if(f[i]==0)
        {
            p.push_back(i);
        }
    }
    cin>>t;
    for(int h=1;h<=t;++h)
    {
        cin>>a>>b;
        int j=0;
        d.clear();
        for(j=0;p[j]*p[j]<=b;++j)
        {
            int c=0;
            while(b%p[j]==0)
            {
                ++c;
                b/=p[j];
            }
            if(c>0)
            {
                d.push_back(p[j]);
            }
            if(b==1)
            {
                break;
            }
        }
        if(p[j]*p[j]>b && b!=1)
        {
            d.push_back(b);
        }
        sum=0;
        long long pt=1,nn=2,pp=d.size();
        while(pp>0)
        {
            if(pp%2==1)
            {
                pt=pt*nn;
            }
            nn=nn*nn;
            pp/=2;
        }
        for(int p=1;p<pt;++p)
        {
            long long nr=p,pr=1;
            int cnt=0,cc=-1;
            while(nr>0)
            {
                ++cc;
                if(nr%2==1)
                {
                    ++cnt;
                    pr*=d[cc];
                }
                nr/=2;
            }
            if(cnt%2==1)
            {
                sum+=a/pr;
            }
            else
            {
                sum-=a/pr;
            }
        }
        cout<<a-sum<<"\n";
    }
    return 0;
}