#include <iostream>
#include <fstream>

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

const int PMAX = 1000000;
int nrp, Prim[PMAX / 2], nrd;
long long divp[13];
bool 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 divizorip(long long x)
{
    nrd = 0;
    for(int i = 1; 1LL * Prim[i]*Prim[i] <= x; i++)
        if(x % Prim[i] == 0)
        {
            divp[++nrd] = Prim[i];
            do
            {
                x /= Prim[i];
            }
            while(x % Prim[i] == 0);
        }
    if(x > 1) divp[++nrd] = x;
}

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