#include <cstdio>
#include <cstring>
#define Max 1000001
#define Mod 9973

int pr[80000],np,fact[20],k;
bool x[20];

void ciur(){
    bool p[Max];
    int i = 2;

    memset(p,0,sizeof(p));
    while( i <= 1000 )
    {
        while(p[i])i++;
        for(int j = i * i;j < Max;j += i)p[j] = 1;
        i++;
    }

    for(i = 2;i < Max;i++)
    if( !p[i] )pr[++np] = i;
}

void desc(long long x){
    int i = 1;
    k = 0;
    while( pr[i] != 0 && pr[i] * pr[i] <= x )
    {
        if(x % pr[i] == 0)
        {
            while(x % pr[i] == 0)x /= pr[i];
            fact[++k] = pr[i];
        }
        i++;
    }
    if(x != 1) fact[++k] = x;
}

void calc(long long a){
    int i, nr = 0;
    long long p = 1, s = 0;
    memset(x,0 ,sizeof(x));
    while( x[k+1] == 0 )
    {
        i = 1;
        while( x[i] ){ x[i] = 0; p /= fact[i]; nr--; i++; }
        p *= fact[i]; nr++;
        x[i] = 1;
        if(x[k+1]==0)
        if(nr%2)s += a/p; else s-=a/p;
    }
    printf("%lld\n",a-s);
}

int main(){
    int t;
    long long a,b;
    ciur();

    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld",&a,&b);
            desc(b);
            calc(a);
          //  for(int i=1;i<=k;i++)printf("%d ",fact[i]);
           // printf("\n");
        }

    return 0;
}