#include <iostream>
#include <fstream>

using namespace std;

const int DIV_MAX = 10;
const int DMAX = 1e6;
const int PRIME = 78498;

long long divv[DIV_MAX];
int prime[PRIME];
char ciur[DMAX + 1];

void calc_ciur() {
    int i, j;
    ciur[0] = ciur[1] = 1;
    for ( i = 2; i * i <= DMAX; i += 1 + i % 2 ) {
        if ( ciur[i] == 0 ) {
            for ( j = i * i; j <= DMAX; j += i )
                ciur[j] = 1;
        }
    }
    j = 0;
    for ( i = 2; i <= DMAX; i ++ ) {
        if ( ciur[i] == 0 )
            prime[j++] = i;
    }
}
int calc_div( long long x ) {
    int d, i;
    i = d = 0;
    while ( (long long)prime[d] * prime[d] <= x ) {
        if ( x % prime[d] == 0 ) {
            divv[i ++] = prime[d];
            while ( x % prime[d] == 0 )
                x /= prime[d];
        }
        d ++;
    }
    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;
    calc_ciur();
    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;
}