#include <iostream>
#include <fstream>

using namespace std;

const int DIV_MAX = 10;

long long divv[DIV_MAX];

int calc_div( long long x ) {
    int d, i;
    i = 0;
    d = 2;
    while ( d * d <= x ) {
        if ( x % d == 0 ) {
            divv[i ++] = d;
            while ( x % d == 0 )
                x /= d;
        }
        d += 1 + d % 2;
    }
    if ( x > 1 )
        divv[i ++] = x;
    return i;
}
long long prod( int j ) {
    long long p = 1;
    int i = 0;
    while ( j > 0 ) {
        if ( j % 2 == 1 ) {
            p *= -divv[i];
        }
        j /= 2;
        i ++;
    }
    return p;
}
int main() {
    ifstream fin( "pinex.in" );
    ofstream fout( "pinex.out" );
    int m, i, j, d;
    long long a, b, ans;
    fin >> m;
    for ( i = 0; i < m; i ++ ) {
        fin >> a >> b;
        d = calc_div( b );
        ans = a;
        for ( j = 1; j < ( 1 << d ); j ++ ) {
            ans += a / prod( j );
        }
        fout << ans << '\n';
    }
    return 0;
}