#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 int a,b;
bool v[MAXP+1];
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 calcsol()
{
    int nt=1<<p.size();
    long long int card=0,prod,t;
    for(int i=1; i<nt; i++)
    {
        prod=1;
        int j=0,p2,ndiv=0;
        while((p2=1<<j)<=i)
        {
            if(p2&i)
            {
                prod*=p[j];
                ndiv++;
            }
            j++;
        }
        t=a/prod;
        if(ndiv%2==0) card-=t;
        else
            card+=t;
    }
    fout<<a-card<<'\n';
}

int main()
{
    generarenrprim(MAXP);
    fin>>m;
    while(m--)
    {
        fin>>a>>b;
        generaredivb();
        calcsol();
    }

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