#include <fstream>
#include <cstdio>
using namespace std;
long long n,srb,i,j,v[1000000],x[1000000],ma,s,k,q[1000000],p,o,in,nr,w[1000000],pd;;
bool pr[100000];
int main(){
    freopen("pinex.in","r",stdin);
    ofstream g ("pinex.out");
    scanf("%d",&n);
    for(i=2;i<=srb;i++)
        pr[i]=true;
    for(i=2;i<=srb;i++)
    if(pr[i]){
            j=i*2;
    while(j<=srb){
            pr[i]=false;
    j+=i;}}
    for(i=1;i<=n;i++){
            scanf("%d%d",&v[i],&x[i]);
            if(x[i]>ma)ma=x[i];}
            for(i=2;i<=ma;i++)
        pr[i]=true;
    for(i=2;i<=ma;i++)
    if(pr[i]){
            j=i*2;
    while(j<=ma){
            pr[j]=false;
    j+=i;}}
     for(i=1;i<=n;i++){
            s=0;
            k=0;
            for(j=2;j<=x[i];j++)
            if(pr[j])
            if(x[i]%j==0){s=s+v[i]/j;
            k++;
            q[k]=j;}
    // if(s==0){s=s+v[i]/x[i];k++;q[k]=x[i];}
    srb=1<<k;
    srb--;
            for(o=1;o<=srb;o++){
            p=o;
            nr=0;
            for(j=0;j<k;j++)
            if(p&(1<<j))nr++;
            if(nr>=2){
                    in=0;
                for(j=0;j<k;j++)
            if(p&(1<<j))
            {in++;
                    w[in]=q[j+1];
            }}
            if(in!=0){
                    pd=1;
            for(j=1;j<=in;j++)
                pd=pd*w[j];
                if(in<k)
            s=s-v[i]/pd;
            else
                if(in==k&&k>2)s=s+v[i]/pd;
            else
                if(in==k)s=s-v[i]/pd;
                in=0;}
                }
                g<<v[i]-s<<'\n';}
            return 0;}