#include <stdio.h>

#define MAX_D 1000000
#define MAX_PRIME 1000000
#define MAX_DIV_PRIMI 12

int divPrimi;
char ciur[MAX_D + 1];
int prime[MAX_PRIME], div[MAX_DIV_PRIMI];

void desc( long long a ) {
    int d, exp;

    d = 0;
    divPrimi = 0;
    while ( a > 1 && prime[d] * prime[d] <= a ) {
        exp = 0;
        while ( a % prime[d] == 0 ) {
            a /= prime[d];
            exp++;
        }
        if ( exp > 0 ) {
            div[divPrimi] = prime[d];
            divPrimi++;
        }
        d++;
    }
    if ( a > 1 ) {
        div[divPrimi] = a;
        divPrimi++;
    }
}

int main() {
    FILE *fin, *fout;
    int t, n, m, nrPrime, semn, i, j;
    long long a, b, x, ans;

    for ( i = 2; i * i <= MAX_D; i++ ) {
        if ( ciur[i] == 0 ) {
            for ( j = i * i; j <= MAX_D; j += i )
                ciur[j] = 1;
        }
    }
    nrPrime = 0;
    for ( i = 2; i <= MAX_D; i++ ) {
        if ( ciur[i] == 0 ) {
            prime[nrPrime] = i;
            nrPrime++;
        }
    }

    fin = fopen( "pinex.in", "r" );
    fout = fopen( "pinex.out", "w" );

    fscanf( fin, "%d", &t );
    for ( i = 0; i < t; i++ ) {
        fscanf( fin, "%lld%lld", &a, &b );

        desc( b );
        n = divPrimi;

        ans = 0;
        for ( m = 0; m < (1 << n); m++ ) {
            x = 1;
            semn = 1;
            for ( j = 0; j < n; j++ ) {
                if ( (m >> j) & 1 == 1 ) {
                    x *= div[j];
                    semn = -semn;
                }
            }
            ans += (a / x) * semn;
        }

        fprintf( fout, "%lld\n", ans );
    }

    fclose( fin );
    fclose( fout );

    return 0;
}