#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 65;
int v[N];

int main ( ) {
    
    int t, n, i, a, b, d, x, mask;
    
    fin >> t;
    
    for ( int k = 0; k < t; k++ ) {
        
        fin >> a >> b;
        
        n = x = 0;
        
        for ( d = 2; 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++ ) {
            
            int 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;
}