#include <bits/stdc++.h>
#define Nmax 1000000
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

vector <int> p;
bitset <Nmax+5> c;
void ciur()
{
    int i, j;
    c[1]=1;
    for(i=2;i*i<=Nmax;i++)
        {
            if(c[i]==0)
            for(j=i;j*i<=Nmax;j++)
                c[i*j]=1;
            p.push_back(i);
        }
}
int nrbiti(int x)
{
    int k=0;
    while(x)
    {
        k++;
        x=x&(x-1);
    }
    return k;
}
int n, k;
long long A, B, s;
int main()
{
    fin >> n;
    ciur();
    while(n--)
    {
        fin >> A >> B;
        vector <int> v;
        int k=0;
        s=0;
        while(k<p.size()&&p[k]*p[k]<=B)
        {
            if(B%p[k]==0)
            {
                v.push_back(p[k]);
                while(B%p[k]==0)
                    B/=p[k];
            }
            k++;
        }
        if(B!=1)
            v.push_back(B);
        for(int i=0;i<(1<<v.size());i++)
        {
            long long prod=1;
            for(int j=0;j<v.size();j++)
                if(i&(1<<j))
                    prod*=v[j];
            int aux=nrbiti(i);
            if(aux%2)
                s-=A/prod;
            else s+=A/prod;
        }
        fout << s << '\n';
    }
    return 0;
}