#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
int main() {
    int t;
    in>>t;
    while(t--){
        ll a, b;
        in>>a>>b;
        vector<int>v;
        for(int i=2; i*i<=b; ++i){
            if(b%i==0){
                v.push_back(i);
                while(b%i==0){
                    b/=i;
                }
            }
        }
        if(b){
            v.push_back(b);
        }
        int s=0;
        for(int i=1; i<(1LL<<((ll)v.size())); i++){
            ll nr=0, x=1;
            for(int j=0; j<62; ++j){
                if(i&(1LL<<j)){
                    nr++;
                    x*=v[j];
                }
            }
            s+=(nr%2==1?1:-1)*(a/x);
        }
        out<<a-s<<"\n";
    }
    return 0;
}