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

using namespace std;

const int PrimeMax = 1e6 + 3 ;

bool ciur [ PrimeMax ];
int primes [ 80000 ] , prcr ;

void PreCalcPrimes (){
    static int i  ;
    long long j ;

    for ( i = 2 ; i < PrimeMax ; i++ ){

        if ( ciur [ i ] == 1 ){
            continue ;
        }

        for ( j = 1LL * i * i ; j < PrimeMax ; j += i ){
            ciur [ j ] = 1 ;
        }
        primes [ prcr ++ ] = i ;
    }

}

int bdiv [ 80000 ] ,divCr ;

long long solve( long long a , long long b ){
    static int i , j ;

    divCr = 0 ;
    for ( i = 0 ; primes [ i ] <= sqrt( b )  ; i++ ){
        if ( b % primes [ i ] == 0 ){
            while ( b % primes [ i ] == 0 ){
                b/= primes [ i ] ;
            }
            bdiv [ ++divCr ] = primes [ i ] ;
        }
    }

    if ( b > 1 ){
        bdiv [ ++divCr ] = b ;
    }

    long long sol = a ;

    long long prod , power ;
    for ( i = 1 ; i < (1 << divCr) ; i++ ){
        prod = 1;
        power = 0 ;
        for ( j= 0 ; j < divCr ; j++ ){
            if ( ( 1 << j ) & i ){
                prod = 1LL * prod * bdiv [ j + 1 ] ;
                power ++ ;
            }
        }

        if ( power % 2 ){
            power = -1 ;
        }else{
            power = 1 ;
        }

        sol = sol +  power * a / prod ;

    }

    return sol ;

}


int main(){
    int noTests ;
    long long a , b ;

    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%d",&noTests);

    PreCalcPrimes ();

    while ( noTests -- ){
        scanf("%lld%lld",&a,&b);

        printf("%lld\n",solve( a , b ) );

    }


    return 0;
}
// Trust me, I'm an Apache Helicopter