#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m;
long long a,b,mask,produs,ans;
vector<int>primes,d;
bool c[1000006];
int main()
{
    fin>>m;
    c[0]=1;
    c[1]=1;
    for(int i=2;i<=1000000;i++)
        if(c[i]==0)
        {
            primes.push_back(i);
            for(int j=2;j<=1000000/i;j++)
                c[i*j]=1;
        }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        ans=0;
        d.clear();
        for(int j=0;j<primes.size();j++)
        {
            if(b%primes[j]==0)
                d.push_back(primes[j]);
            if(primes[j]>b)
                break;
        }
        for(mask=1;mask<(1<<d.size());mask++)
        {
            int nr=0;
            produs=1;
            for(int j=0;j<d.size();j++)
                if((mask>>j)&1)
                {
                    nr++;
                    produs*=d[j];
                }
            if(nr%2==1)
                ans+=a/produs;
            else
                ans-=a/produs;
        }
        fout<<a-ans<<'\n';
    }
    return 0;
}