#include <fstream>
#include <vector>
#define DIM 1000002

using namespace std;

ifstream in ("pinex.in");
ofstream out("pinex.out");
             
long long n, ciur[DIM + 2];

long long a, b, B;

vector<long long> prim, diviz;

bool test(int i, int j){
    return i & (1<<j);
}

int main(int argc, const char * argv[]) {
    
    in>>n;
    
    for(int i = 2; i * i <= DIM; ++ i){
        if(!ciur[i]){
            for(int j = i + i; j <= DIM; j += i)
                ciur[j] = 1;
        }
    }
    
    for(int i = 2; i <= DIM; ++ i)
        if(!ciur[i])
            prim.push_back(i);
    
    while(n--){
        in>>a>>b;
        diviz.clear();
        B = b;
        long long sol = 0;
        for(int i = 0; i < prim.size() && prim[i] * prim[i] <= b && B > 1; ++ i){
            if(B % prim[i] == 0){
                diviz.push_back(prim[i]);
                while(B % prim[i] == 0)
                    B /= prim[i];
            }
        }
        
        if(B > 1)
            diviz.push_back(B);
        
        long long dim = (1<<(diviz.size())) - 1;
        long long nrdiv = diviz.size();
        
        for(int i = 1; i <= dim; ++ i){
            long long prod = 1;
            int nr = 0;
            for(int j = 0; j < nrdiv; ++ j){
                if(test(i, j)){
                    prod = prod * 1LL * diviz[j];
                    ++ nr;
                }
            }
            if(nr % 2)
                sol += (a / prod);
            else
                sol -= (a / prod);
        }
        
        out<<(long long)a - sol<<'\n';
        
    }
    
    
    
    return 0;
}