#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(x) cout << #x <<": " << x << "\n";
#define sz(x) ((int)x.size())

using ll = long long;

const string fn = "pinex";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int tc;
bitset<1000005> prime;
vector<int> primes;
void sieve(){

    prime[0] = prime[1] = 1;
    for (int i = 4; i <= 1e6; i += 2)
        prime[i] = 1;

    for (int i = 3; i * i <= 1e6; i += 2)
        if(prime[i] == 0)
            for (int j = i * i; j <= 1e6; j += i + i)
                prime[j] = 1;

    prime.flip();
    for (int i = 2; i <= 1e6; ++i)
        if(prime[i])
            primes.pb(i);
}


void solve(ll a, ll b){

    ll ans = 0;
    int p = 0;
    ll f = primes[p];
    
    vector<ll> factors;
    while(b > 1 && f * f <= b){
        if(b % f == 0){
            while(b % f == 0)
                b /= f;
            factors.pb(f);
        }
        f = primes[++p];
    }

    if(b > 1){
        factors.pb(b);
    }

    int nr = sz(factors);
    for (int i = 1; i <= (1 << nr) - 1; ++i){
        ll prod = 1;
        ll ct = 0;
        for (int j = 0; j < nr; ++j)
            if(((i >> j) & 1)){
                ct++;
                prod = prod * factors[j];
            }
        if(ct % 2 == 1)
            ans += a / prod;
        else
            ans -= a / prod;
    }

    fout << a - ans << '\n';    
}

int main(){

    fin >> tc;
    sieve();
    while(tc--){
        ll a, b;
        fin >> a >> b;
        solve(a, b);
    }

    return 0;
}