# include <stdio.h>
# include <stdlib.h>

# define MAX_PRIMES 500000
# define MAX_B 1500000

long long a, b;

long long fact[50];
int fact_length;

int prime[MAX_PRIMES];
int prime_length;

char ciur[MAX_B];

void descompune( long long val, long long * fact, int * fact_length, int * prime, int prime_length ) {
    int i;

    *fact_length = 0;
    i = 0;
    while ( prime[i] * prime[i] <= val ) {
        if ( val % prime[i] == 0 ) {
            fact[*fact_length] = prime[i];
            ( *fact_length ) ++;

            do {
                val /= prime[i];
            } while ( val % prime[i] == 0 );
        }
        i ++;
    }

    if ( val > 1 ) {
        fact[*fact_length] = val;
        ( *fact_length ) ++;
    }
}

void generate_primes( int * prime, int * prime_length, int n ) {
    int i, j;

    ciur[0] = ciur[1] = 1;
    *prime_length = 0;

    for ( i = 0; i * i < n; i ++ )
        if ( !ciur[i] ) {
            prime[*prime_length] = i;
            ( *prime_length ) ++;

            for ( j = i * i; j < n; j += i )
                ciur[j] = 1;
        }

    for ( ; i < n; i ++ )
        if ( !ciur[i] ) {
            prime[*prime_length] = i;
            ( *prime_length ) ++;
        }
}

int main() {
    FILE *fin = fopen( "pinex.in", "r" ), *fout = fopen( "pinex.out", "w" );

    int n, k, i, j, S, semn, p;

    fscanf( fin, "%d", &n );

    generate_primes( prime, &prime_length, MAX_B );

    for ( k = 0; k < n; k ++ ) {
        fscanf( fin, "%lld%lld", &a, &b );

        descompune( b, fact, &fact_length, prime, prime_length );
        S = 0;
        for ( i = 1; i < ( 1 << fact_length ); i ++ ) {
            semn = -1;
            p = 1;
            for ( j = 0; j < fact_length; j ++ ) {
                if ( i & ( 1 << j ) ) {
                    semn = -semn;
                    p *= fact[j];
                }
            }

            S += semn * a / p;
        }

        fprintf( fout, "%lld\n", a - S );
    }

    fclose( fin );
    fclose( fout );

    return 0;
}