#include <fstream>
#define int long long
#define dim (int)(1e6+1)
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int q,a,b,p[dim],prim[dim],n,m,total;
bool ciur[dim];
void pinex(int val,int nr,int last){
    if(nr!=0){
        if(nr%2==0)
            total-=a/val;
        else
            total+=a/val;
    }
    for(int i=last+1;i<=m;i++)
        pinex(val*p[i],nr+1,i);
}
signed main()
{
    cin>>q;
    for(int i=2;i<dim;i++)
        if(!ciur[i]){
            prim[++n]=i;
            for(int j=2*i;j<=n;j+=i)
                ciur[j]=1;
        }
    while(q--){
        cin>>a>>b;
        m=0;
        for(int i=1;prim[i]*prim[i]<=b;i++)
            if(b%prim[i]==0){
                p[++m]=prim[i];
                while(b%prim[i]==0)
                    b/=prim[i];
            }
        if(b!=1)
            p[++m]=b;
        total=0;
        pinex(1,0,0);
        cout<<a-total<<'\n';
    }
    return 0;
}