#include <fstream>
#include <vector>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long m, a, b, i, j, d, n, ans, mask, pr, nr;
int main()
{
    fin>>m;
    while(m--)
    {
        fin>>a>>b;
        int ca=b, d=2;
        vector <int> div;
        while(ca>1)
        {
            if(ca%d==0)
            {
                div.push_back(d);
                while(ca%d==0)
                    ca/=d;
            }
            d++;
            if(d*d>ca)
                d=ca;
        }
        n=div.size(), ans=0;
        for(mask=0; mask<(1<<n); mask++)
        {
            pr=1, nr=0;
            for(int i=0; i<n; i++)
                if(mask&(1<<i))
                {
                    pr*=div[i];
                    nr++;
                }
            if(pr>1)
            {
                if(nr%2==1)
                    ans+=a/pr;
                else
                    ans-=a/pr;
            }

        }
        fout<<a-ans<<'\n';


    }
    return 0;
}