#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define INFILE "pinex.in"
#define OUTFILE "pinex.out"

const int N_MAX = 1e6 + 5;

vector<int> primes;

void init(){

    vector<bool> ciur(N_MAX, true);

    ciur[0] = ciur[1] = false;

    for(int d = 2; d < N_MAX; ++d){
        if(ciur[d]){
            primes.push_back(d);
            for(ll i = 1LL * d * d; i < N_MAX; i += d) ciur[i] = false;
        }
    }

}

void solve(){

    ll a, b; cin >> a >> b;

    vector<int> divs;

    bool ok = true;
    for(int i = 0; i < primes.size() && ok; ++i){
        int d = primes[i];
        if(1LL * d * d > b){
            ok = false;
        }
        else {

            if(b % d == 0){
                divs.push_back(d);
                while(b % d == 0) b /= d;
            }

        }
    }

    if(b > 1){
        divs.push_back(b);
        b = 1;
    }

    int n = divs.size();
    ll ans = 0;

    for(int mask = 1; mask < (1 << n); ++mask){

        int sign = -1;
        ll product = 1;

        for(int i = 0; i < n; ++i){
            int good = ((mask >> i) & 1);
            if(good) sign *= -1, product *= divs[i];
        }

        ans += sign * (a / product);

    }

    cout << a - ans << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    #ifdef ONLINE_JUDGE
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    #endif
    cin.tie(0), cout.tie();
    init();
    int tests; cin >> tests;
    for(int i = 0; i < tests; ++i) solve();
    return 0;
}