#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ( "pinex.in" );
ofstream fout ( "pinex.out" );

const int N = 1e6;
long long v[65];
int ciur[N], prime[N];


int main ( ) {
    
    int c = 0;
    for ( long long i = 2; i < N; i++ ) {
        if ( ciur[i] == 0 ) {
            prime[c] = i;
            for ( long long j = i * i; j < N; j = j + i )
                ciur[j] = 1;
            c++;
        }
    }
    
    long long t, n, i, a, b, d, x, mask;
    
    fin >> t;
    
    for ( int k = 0; k < t; k++ ) {
        
        fin >> a >> b;
        
        n = x = 0;
        
        for ( i = 0; i < c; i++ ) {
            
            if ( b % prime[i] == 0 ) {
                v[x] = prime[i];
                x++;
            }
            
            while ( b % prime[i] == 0 )
                b = b / prime[i];
        }
            
        for ( d = N; d * d <= b; d++ ){
            
            if ( b % d == 0 ) {
                v[x] = d;
                x++;
            }
            
            while ( b % d == 0 )
                b = b / d;
        }
        
        if ( b > 1 )
            v[x++] = b;
        
        for ( mask = 0; mask < ( 1 << x ); mask++ ) {
            
            long long s = 1, p = 1;
            
            for( i = 0; i < x; i++ ) {
                if ( ( mask >> i ) & 1 ) {
                    s = -s;
                    p = p * v[i];
                }
            }
            
            n = n + a / p * s;
        }
        
        fout << n << "\n";
        
    }
    
    return 0;
}