#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");

long long n,i;

vector<long long> fact(long long nr)
{
    long long d=2;
    vector<long long>primi;
    while(nr>1)
    {
        bool intrat=0;
        while(nr%d==0)
        {
            nr/=d;
            intrat=1;
        }
        if(intrat)
            primi.push_back(d);

        d++;
        if(d*d>=nr)
            d=nr;
    }
    return primi;
}

int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        long long a,b;
        vector<long long>primi;
        cin>>a>>b;
        primi = fact(b);

        long long k=primi.size(),rsp=0;
        for(long long mask=1;mask<(1<<k);mask++)
        {
            long long p=1,nr=0;
            for(long long j=0;j<k;j++)
                if((mask&(1<<(j))))
                    nr++,p*=primi[j];
            if(nr%2==1)
                rsp+=a/p;
            else
                rsp-=a/p;
        }
        cout<<a-rsp<<'\n';
    }
    return 0;
}