#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 prim = nrPrime[cntFactori];

    while(prim < sqrt(nr))
    {
        if(nr % prim == 0)
        {           
            while(nr % prim == 0)
                nr /= prim;

            fact[cntFactori] = prim;
        }
        prim = nrPrime[++cntFactori];
    }

    if(nr % prim == 0)
    {
        fact[cntFactori] = prim;
        ++cntFactori;
    }
    
}

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

#ifdef DEBUG
cout<<cntFactori<<endl;
for(int i=0;i<cntFactori;i++)
    cout<<fact[i];
cout<<endl;
cout<<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();

/*  for(int i=0;i<10;i++)
        cout<<nrPrime[i]<<" ";
*/
  
    fact = new int[cntNrPrime];

/*
    factori(30);
    for(int i=0;i<cntFactori;i++)
        cout<<fact[i]<<" ";
*/


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

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

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