#include <iostream>
#include <fstream>
#include <math.h>

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

const int prim = 1000000;
long long n, a, b, nrprim, nr, d, p[prim+5], sol, fact[prim+5], seen[prim+5];

void Precalc()
{
    seen[0] = seen[1] = 1;
    for(int i = 2; i <= prim; i++)
    {
        if(seen[i] == 0)
        {
            for(int j = 2*i; j <= prim; j=j+i) seen[j] = 0;
            p[++nrprim] = i;
        }
    }
}

void Solve()
{
    nr = 0;
    d = 0;
    while(b>1)
    {
        //cout<<b<<' ';
        d++;
        if(b%p[d] == 0)
        {
            fact[nr++] = p[d];
            while(b%p[d] == 0)
            {
                b /= p[d];
            }
        }
        if(p[d]>sqrt(b) && b>1)
        {
            fact[nr++] = b;
            b = 1;
        }
    }
    sol = a;
    for(long long i = 1; i < (1<<nr); i++)
    {
        long long m = 0, prod = 1;
        for(int j = 0; j < nr; j++)
        {
            if((1<<j) & i)
            {
                prod = prod*1LL*fact[j];
                m++;
            }
        }
        if(m%2 == 1) m = -1;
        else m = 1;
        sol = sol + 1LL*m*a/prod;
    }
    g<<sol<<'\n';
}

int main()
{
    f>>n;
    Precalc();
    //for(int i = 0; i<nr; i++) cout<<p[i]<<' ';
    while(n--)
    {
        f>>a>>b;
        //cout<<a<<b;
        Solve();
    }
    return 0;
}