#include <bits/stdc++.h>

using namespace std;

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

const int PMAX = 1e6;

bitset <PMAX + 1> ciur;

vector <int> prime;

vector <long long> getPrimeDivs( long long x ) {
    vector <long long> divs;

    for ( auto d : prime ) {
        if ( (long long)d * d > x ) break;
        if ( x % d == 0 ) {
            while ( x % d == 0 ) x /= d;
            divs.push_back( d );
        }
    }
    if ( x > 1 ) divs.push_back( x );
    return divs;
}
void solve() {
    long long a, b;
    fin >> a >> b;

    auto divs = getPrimeDivs( b );
    int n = (1 << divs.size());
    long long ans = 0;
    for ( int mask = 0; mask < n; mask ++ ) {
        long long prod = 1;
        for ( int i = 0; i < (int)divs.size(); i ++ ) {
            if ( mask & (1 << i) ) prod *= -divs[i];
        }
        ans += a / prod;
    }
    fout << ans << '\n';
}
int main() {
    int t;

    fin >> t;    
    ciur[0] = ciur[1] = 1;
    for ( int i = 2; i * i <= PMAX; i ++ ) {
        if ( !ciur[i] ) {
            for ( int j = i * i; j <= PMAX; j += i ) {
                ciur[j] = true;
            }
        }
    }
    for ( int i = 2; i <= PMAX; i ++ ) {
        if ( !ciur[i] ) {

            prime.push_back( i );
        }
    }
    while ( t-- ) solve();
    return 0;
}

/*
1
10 5
20 6
50 30
*/