#include <fstream>
#include <vector>
#include <bitset>
#define maxsq 1000000
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long sol,a,b;
int d[100],nrd;
bitset <maxsq+100> ciur;
vector <int> p;


void eratosthene()
{
    int i,j;
    ciur[2]=1;
    for (i=3;i<=maxsq;i+=2)
        ciur[i]=1;
    p.push_back(2);
    for (i=3;i*i<=maxsq;i+=2)
        if (ciur[i]==1) {
            for (j=i*i;j<=maxsq;j+=i)
                ciur[j]=0;
        }
    for (i=3;i<=maxsq;i+=2)
        if (ciur[i])
            p.push_back(i);
}
void generare(int nrb,int nrt,long long k)
{
    if (nrb<=nrd) {
        generare(nrb+1,nrt+1,1LL*k*d[nrb]);
        generare(nrb+1,nrt,k);
        return;
    }
    if (nrt%2==1)
        sol-=1LL*a/k;
    else
        sol+=1LL*a/k;
}
void solve()
{
    int i;
    sol=0;nrd=0;
    f>>a>>b;
    for (i=0;i<p.size()&&b-1;i++) {
        if (b%p[i]==0) {
            b/=p[i];
            d[++nrd]=p[i];
            while (b%p[i]==0)
                b/=p[i];
        }
        else
            if (b<p[i]*p[i]) {
                d[++nrd]=b;
                b=1;
            }
    }
    generare(1,0,1);
    g<<sol<<'\n';
}
int main()
{
    int q;
    eratosthene();
    for (f>>q;q;q--)
        solve();
    return 0;
}