#include <iostream>
#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

const int MAXP = 1000000;//Margine superioara pentru cel mai mare numar prim
const int NMAX = 100000; //Margine superioara pentru numarul maxim de numere prime
const int NDIV = 13;     //Margine superioara pentru numarul maxim de divizori primi

int M; //Datele de intrare
long long int A, B ;

bool b[MAXP]; //Vector pentru Ciurul lui Eratostene
int prim[NMAX], lp = 0; //Vectorul numerelor prime
int p[NDIV], lg;  //Vectorul divizorilor primi ai lui B

void generareNumerePrime()
{
    int i, j;
    for(i = 4; i < MAXP; i += 2)
        b[i] = 1;
    for(i = 3; i * i < MAXP; i += 2)
        if(b[i] == 0)
            for(j = i * i; j < MAXP; j += i)
                b[j] = 1;
    for(i = 2; i < MAXP; i++)
        if(b[i] == 0) prim[++lp] = i;
}

void generareDivizoriB()
{
    lg = 0;
    for(int j = 1; 1LL * prim[j]*prim[j] <= B; j++)
        if(B % prim[j] == 0)
        {
            p[++lg] = prim[j];
            while(B % prim[j] == 0) B /= prim[j];
        }
    if(B > 1)p[++lg] = B;
}

int main()
{
    generareNumerePrime();
    f >> M;
    while(M--)
    {
        f >> A >> B;
        generareDivizoriB();
        int nt = 1 << lg;
        long long int card = 0;
        for(int i = 1; i < nt; i++)
        {
            long long int prod = 1;
            int j = 0, p2, ndiv = 0;
            while((p2 = 1 << j) <= i)
            {
                if(p2 & i)
                {
                    prod *= p[j + 1];
                    ndiv++;
                }
                j++;
            }
            long long int t = A / prod;
            if(ndiv % 2 == 0)
                card -= t;
            else
                card += t;
        }
        g << A - card << '\n';
    }
    f.close();
    g.close();
    return 0;
}