#include <cstdio>
#include <cstring>

#define MAX 1000001
#define MOD 9973

int pr[80000],nrr,fact[30],n,bit[30];

void ciur(){
    bool p[MAX];
    int i = 2;
    while( i <= 1000 )
    {
        while( p[i] )i++;
        for(int j=i*i;j<MAX;j+=i) p[j] = 1;
        i++;
    }
    for(int i=2;i<MAX;i++)
    if( !p[i] )pr[++nrr] = i;
}

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

void raspuns(long long a){
    long long prd = 1,rasp = 0;
    int i = 1, nr = 0;

    memset(bit,0,sizeof(bit));

    while( bit[n+1] == 0 )
    {
        i = 1; while (bit[i]) {nr--; bit[i] = 0; prd/=fact[i]; i++; }
        bit[i] = 1;
        nr ++;
        prd *= fact[i];
       // printf("%lld ",prd);
    if( bit[n+1] == 0)
    if( nr % 2 )rasp += a/prd; else rasp -= a/prd;
    }
    printf("%lld\n",a-rasp);
//printf("\n");
}

int main(){
    long long a,b;
    int t;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    ciur();
        scanf("%d",&t);
        while(t--)
        {
            scanf("%lld %lld",&a,&b);
            desc(b);
            raspuns(a);
        }
    return 0;
}