#include <bits/stdc++.h>

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

int64_t A,B;
vector <int64_t> P;
bitset <1000005> v;
int m;
int main()
{
    P.push_back(2);
    for(int i=3; i<=1000000; i+=2)
        if(!v[i])
        {
            for(int j=2; i*j<=1000000; j++)
                v[i*j]=1;
            P.push_back(i);
        }
    f>>m;
    while(m--)
    {
        f>>A>>B;
        int h=0;
        vector <int64_t> S;
        while(B>1)
        {
            if(!(B%P[h]))
            {
                S.push_back(P[h]);
                while(!(B%P[h]))
                    B/=P[h];
            }
            h++;
            if(P[h]*P[h]>B&&B>1)
            {
                S.push_back(B);
                break;
            }
        }
        int64_t Rez=0;
        for(int i=1; i<(1<<S.size()); i++)
        {
            int64_t Prod=1;
            int Size=__builtin_popcount(i);
            for(int j=0; j<S.size(); j++)
            {
                if(i&(1<<j))
                    Prod*=S[j];
            }
            if(Size&1)
                Rez+=A/Prod;
            else
                Rez-=A/Prod;
            //g<<Prod<<','<<Rez<<' ';
        }
        g<<A-Rez<<'\n';

    }

    return 0;
}