#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int MAXP=1000000;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m;
long long a,b,card;
bool v[MAXP+1];
int x[20];
vector<int>prim;
vector<int>p;

void generarenrprim(int n)
{
    for(int i=3; i*i<=n; i+=2)
        if(v[i]==0)
            for(int j=i*i; j<=n; j+=2*i)
                v[j]=1;
    prim.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(v[i]==0)
            prim.push_back(i);
}

void generaredivb()
{
    p.clear();
    for(unsigned i=0; 1LL*prim[i]*prim[i]<=b; i++)
        if(b%prim[i]==0)
        {
            p.push_back(prim[i]);
            do
                b/=prim[i];
            while(b%prim[i]==0);
        }
    if(b>1) p.push_back(b);
}

void bt(int k, long long prod)
{
    long long t1,t2;
    for(int i=x[k-1]+1; i<(int)p.size(); i++)
    {
        x[k]=i;
        t1=prod*p[i];
        t2=a/t1;
        if(k%2==0) card-=t2;
        else
            card+=t2;
        bt(k+1,t1);
    }
}

int main()
{
    generarenrprim(MAXP);
    fin>>m;
    while(m--)
    {
        fin>>a>>b;
        generaredivb();
        card=0;
        x[0]=-1;
        bt(1,1LL);
        fout<<a-card<<'\n';
    }

    fin.close();
    fout.close();
    return 0;
}