#include <bits/stdc++.h>

using namespace std;

#define int long long
int v[20], x[20];
ifstream fin( "pinex.in" );
ofstream fout( "pinex.out" );

int m, sum, a;

void calc( int k ) {
    int i, p = 1;
    for( i = 1; i <= k; i++ )
        p = p * v[x[i]];
    p = a / p;
    if( k & 1 )
        sum += p;
    else
        sum -= p;
}

void bkt( int k ) {
    int i;
    for( i = x[k - 1] + 1; i <= m; i++ ) {
        x[k] = i;
        calc( k );
        bkt( k + 1 );
    }
}

signed main() {
    int n, b, p, d, i;

    fin >> n;
    for( i = 1; i <= n; i++ ) {
        fin >> a >> b;
        d = 2;
        m = 0;
        while( d * d <= b ) {
            p = 0;
            while( b % d == 0 )
                b /= d, p++;
            if( p > 0 )
                v[++m] = d;
            d++;
        }
        if( b > 1 )
            v[++m] = b;
        sum = 0;
        bkt( 1 );
        fout << a - sum << '\n';
    }
    return 0;
}