#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
const int PMAX = 1000001, NMAX = 80000;
int Prim[NMAX], nrp, ndiv;
long long Div[13];
char v[PMAX];

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 divprim(int b)
{
    int i = 1;
    ndiv = 0;
    while(1LL * Prim[i]*Prim[i] <= b)
    {
        if(b % Prim[i] == 0)
        {
            Div[++ndiv] = Prim[i];
            do b /= Prim[i];
            while(b % Prim[i] == 0);
        }
        i++;
    }
    if(b > 1)Div[++ndiv] = b;
}

int main()
{
    long long a, b;
    int m;
    ciur();
    f >> m;
    while(m--)
    {
        f >> a >> b;
        divprim(b);
        long long card = 0;
        int nt = 1 << ndiv;
        for(int i = 1; i < nt; i++)
        {
            long long prod = 1;
            int  nfact = 0,p2;
            for(int j = 0; (p2 = 1 << j) <= i; j++)
                if(p2 & i)
                {
                    prod *= Div[j + 1];
                    nfact++;
                }
            long long t = a / prod;
            if(nfact % 2 == 0)card -= t;
            else card += t;
        }
        g << a - card << endl;
    }
    return 0;
}