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

int a, b;
int fact[20];
int fact_length;

void descompune( void ) {
    fact_length = 0;

    int i;

    if ( b % 2 == 0 ) {
        while ( b % 2 == 0 )
            b /= 2;

        fact[0] = 2;
        fact_length = 1;
    }
    i = 3;

    while ( i * i <= b ) {
        if ( b % i == 0 ) {
            while ( b % i == 0 )
                b /= i;

            fact[fact_length] = i;
            fact_length ++;
        }

        i += 2;
    }

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

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

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

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

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

        descompune();

        S = 0;
        for ( i = 1; i < ( 1 << fact_length ); i ++ ) {
            s = 0;
            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, "%d\n", a - S );
    }

    fclose( fin );
    fclose( fout );

    return 0;
}