#include <fstream>
#include <vector>
#include <cmath>
#define D 1000005

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

vector <int> G;
vector <int> Div;

int n, a, b, sumtot;

bool C[D];

void Ciur()
{
    int i, j;
    for (i=4; i<D; i+=2)
        C[i]=1;
    G.push_back(2);
    for (i=3; i<D; i+=2)
    {
        if (C[i]==0)
        {
            for (j=i; j<D; j+=2*i)
            {
                C[j]=1;
            }
            C[i]=0;
            G.push_back(i);
        }
    }
}

void Find()
{
    int sz=G.size(), i;
    Div.clear();
    for (i=0; i<sz; i++)
    {
        if (b<G[i])
            break;
        if (b%G[i]==0)
        {
            Div.push_back(G[i]);
        }
    }
    int ds=Div.size(), k;
    int prod, ci, nr;
    int limd=pow(2, ds);
    for (i=1; i<limd; i++)
    {
        ci=i;
        k=0;
        prod=1;
        nr=0;
        while (ci>0)
        {
            if (ci%2==1)
            {
                prod *= Div[k];
                nr++;
            }
            ci=ci/2;
            k++;
        }
        if (nr%2==1)
            sumtot += a/prod;
        else
            sumtot -= a/prod;
    }
}

int main()
{
    int i;
    fin>>n;
    Ciur();
    for (i=1; i<=n; i++)
    {
        fin>>a>>b;
        sumtot=0;
        Find();
        fout<<a-sumtot<<'\n';
    }
    return 0;
}