include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,a,b,rez,nrc,p;
vector<int> prime;
void ciur()
{
    vector<bool> eprim(1000001,true);
    eprim[0]=eprim[1]=0;
    for(int i=2;i<=1000001;i++)
        if(eprim[i])
    {
        prime.push_back(i);
        for(int j=i*i;j<=1000001;j+=i)
            eprim[j]=0;
    }
}
signed main()
{
    f>>m;
    ciur();
    while(m--)
    {
        f>>a>>b;
        vector<int> v;
        for(int x:prime)
        {
            if(b%x==0)
        {
            v.push_back(x);
            while(b%x==0)
                b/=x;
        }
        if(x*x>b)
            break;
        }
        if(b>1)
            v.push_back(b);
        rez=a;
        for(int i=1;i<(1LL<<v.size());i++)
        {
            nrc=0;
            p=1;
            for(int j=0;j<v.size();j++)
                if(i & (1LL<<j))
            {
                nrc++;
                p=p*v[j];
            }
            if(nrc%2==1)
                rez=rez-a/p;
            else rez=rez+a/p;
        }
        g<<rez<<'\n';
    }
    return 0;
}