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