#include <fstream>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long t, a, b, divi[5005], i, sum, p, k, pr, nr, mask;
int main()
{
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        p=2;
        k=0;
        sum=0;
        while(b>1)
        {
            if(b%p==0)
            {
                divi[k++]=p;
                while(b%p==0)
                    b/=p;
            }
            p++;
            if(p*p>b && b>1)
                p=b;
        }
        for(mask=0; mask<(1<<k); mask++)
        {
            nr=0, pr=1;
            for(int j=0; j<k; j++)
                if(mask&(1<<j))
                {
                    nr++;
                    pr*=divi[j];
                }
            if(nr!=0)
            {
                if(nr%2)
                    sum+=a/pr;
                else
                    sum-=a/pr;
            }
        }
        fout<<a-sum<<'\n';
    }
    return 0;
}