#include<iostream>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
#define MAX 1000000
#define ll long long
ll M;
ll A,B;
ll R;
bool *prim;
int  nrPrime[MAX];
int cntNrPrime = 0;

int *fact;
int cntFactori = 0;

void ciur()
{
    for(int i=2;i<MAX/2;i++)
        if(prim[i])
        {
            nrPrime[cntNrPrime++] = i;
            int j = 2;
            while( i * j < MAX)
            {
                prim[i*j] = false;
                j++;
            }
        }  

}

void factori(ll nr)
{
    cntFactori = 0;
    int cnt = 0;
    int prim = nrPrime[cntFactori];
    ll L = sqrt(nr);
#ifdef DEBUG
    cout<<nr<<" "<<(int)sqrt(nr)<<endl;
#endif

    while(nr > 1)
    {
#ifdef DEBUG
cout<<prim<<" ";
#endif
        if(nr % prim == 0)
        {
            fact[cntFactori++] = prim;
            while(nr%prim == 0)
            {
                nr /= prim;
            }
        }
        prim = nrPrime[++cnt];

        if(prim>L)
        {
            fact[cntFactori++] = nr;
            nr = 1;
        }
    }

#ifdef DEBUG
    cout<<endl;
#endif
}

void rezolva()
{
    int combinatii = (1<<(cntFactori)) - 1;

#ifdef DEBUG
cout<<"rezolva()"<<endl;
cout<<cntFactori<<endl;
for(int i=0;i<cntFactori;i++)
    cout<<fact[i]<<" ";
cout<<endl;
cout<<"combinatii:"<<combinatii<<endl;
#endif
    int nr;
    ll prod;
    for(int i=1;i<=combinatii;i++)
    {
        prod = 1;
        nr = 0;

        for(int j=0;j<cntFactori;j++)
            if(i & (1<<j))
            {
                prod *= (ll)fact[j];
                nr++;
            }
#ifdef DEBUG
        cout<<prod<<endl;
#endif

        if(nr%2 == 1)
        {
             R += A/prod;
        }
        else
             R -= A/prod;
    }
}

int main()
{
    fstream fin;
    ofstream fout;
    fin.open("pinex.in");
    fin>>M;

    fout.open("pinex.out");

    prim = new bool[MAX];
    memset(prim, true, MAX);
    ciur();

    fact = new int[cntNrPrime];

    for(int i=0;i<M;i++)
    {
        fin>>A>>B;

        factori(B);
        R = 0;
        rezolva();
        fout<<A-R<<endl;
    }

    delete[] prim;
    delete[] fact;
    fout.close();
    fin.close();
    return 0;
}