#include <iostream>
#include <fstream>
#include <vector>

const int MAXN = 1e6 + 1;

using namespace std;

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

typedef long long ll;

bool ciur[MAXN];
ll prime[MAXN],index;
vector<ll>divs;

void creaza_ciur(){
    for(int i = 2; i <= MAXN; i++){
        if(!ciur[i]){
            prime[++index] = i;
            for(int j = i + i; j <= MAXN; j += i)
                ciur[j] = true;
        }
    }
    ll nr = 1;
    for(int i = 1; i <= 30; i++)
        nr *= prime[i];
}
void divizori(ll n){
    int index = 1;
    ll d = 2,exp = 0;

    while(d * d <= n){
        exp = 0;
        while(n % d == 0){
            n /= d;
            exp++;
        }
        if(exp){
            divs.emplace_back(d);
        }
        index++;
        d = prime[index];
    }

    if(n > 1)
        divs.emplace_back(n);
}
ll pinex(ll numar){
    int maxim = divs.size();
    ll ans = 0;
    //for(auto a : divs) cout<<a<<" ";


    for(int i = 1; i < (1<<(maxim)); i++){

        ll prod = 1;
        int cnt = 0;
        for(int j = 0; j < maxim; j++){
            if((i & (1<<j)) > 0){
                prod *= divs[j];
                cnt++;
            }
        }
        //cout<<i<<" : "<<prod<<endl;
        if(cnt & 1)
            ans += numar / prod;
        else
            ans -= numar / prod;
    }
    return ans;
}

int main()
{
    creaza_ciur();
    int t;
    in>>t;
    for(int i = 1; i <= t; i++){
        ll a,b;
        in>>a>>b;
        divs.clear();
        divizori(b);
        out<<a - pinex(a)<<"\n";
    }
    return 0;
}