#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int n,x,y,s,vp[1000001],nrp,vprim[78499];
vector <int> v;
void exec (int l,int imp,int poz,int cur,int &s)
{
    if (cur==l+1)
    {
        if (l%2==1)
        {
            s+=x/imp;
        }
        else s=s-x/imp;
    }
    else
    {
        for (int t=poz; t<v.size(); t++)
        {
            exec(l,imp*v[t],t+1,cur+1,s);
        }
    }
}
int main()
{
    for (int i=2; i<=1000000; i++)
    {
        if (vp[i]==0)
        {
            nrp++;
            vprim[nrp]=i;
            //cout<<i<<'\n';
            for (int j=i*2; j<=1000000; j+=i)
            {
                vp[j]=1;
            }
        }
    }
    //cout<<nrp;
    f>>n;
    for (int i=1; i<=n; i++)
    {
        s=0;
        v.erase(v.begin(),v.end());
        f>>x>>y;
        if (vp[y]==1)
        {
        for (int t=1; t<=nrp && t*t<=y; t++)
        {
            if (y%vprim[t]==0)
            {
                v.push_back(vprim[t]);
               // cout<<vprim[t]<<' ';
            }
        }
        }
        else v.push_back(y);
        for (int l=1; l<=v.size(); l++)
        {
            exec(l,1,0,1,s);
            //cout<<s<<'\n';
        }
        g<<x-s<<'\n';
        /*for (int t=0; t<v.size(); t++)
        {
            cout<<v[t]<<' ';
        }
        cout<<'\n';*/
    }
    return 0;
}