#include <iostream>
#include <fstream>
using namespace std;

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


const int PMAX = 1000000;

long long int A, B, divB[13];
int nrdiv, nrp, M;
unsigned char v[PMAX + 1];
int Prim[PMAX / 3]; //Numerele prime generate

void ciur()
{
    int i, j;
    for(i = 4; i <= PMAX; i += 2)
        v[i] = 1;
    for(i = 3; i * i <= PMAX; i += 2)
        if(v[i] == 0)
            for(j = i * i; j <= PMAX; j += i)
                v[j] = 1;
    nrp = 1;
    Prim[1] = 2;
    for(i = 3; i <= PMAX; i += 2)
        if(v[i] == 0)Prim[++nrp] = i;
}


void divizoriB(long long int B)
{
    int i = 1;
    nrdiv = 0;
    while(1LL * Prim[i] * Prim[i] <= B)
    {
        if(B % Prim[i] == 0)
        {
            divB[++nrdiv] = Prim[i];
            do
                B = B / Prim[i];
            while(B % Prim[i] == 0);
        }
        i++;
    }
    if(B > 1)
        divB[++nrdiv] = B;
}

int main()
{
    ciur();
    f >> M;
    for(int i = 1; i <= M; i++)
    {
        f >> A >> B;
        divizoriB(B);
        long long card = 0;
        int nt = (1 << nrdiv);
        for(int k = 1; k < nt; k++)
        {
            long long produs = 1;
            int nrbiti = 0, p2;
            for(int j = 0; (p2 = 1 << j) <= k; j++)
                if(p2 & k)
                {
                    produs *= divB[j + 1];
                    nrbiti++;
                }
            long long T = A / produs;
            if(nrbiti % 2 == 0) card -= T;
            else card += T;
        }
        g << A - card << '\n';
    }
    return 0;
}