#include<bits/stdc++.h>

using namespace std;

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

int auxciur[1000002];
long long nrprime[100000];
long long divpB[10000];
int k;

void ciur(){
    int i,j;
    for(i = 2; i <= 1001; i++){
        if(!auxciur[i]){
            nrprime[k] = i;
            k++;
            for(j = i*i; j <= 1000000; j += i){
                auxciur[j] = 1;
            }
        }
    }
    for(i = 1003; i <= 1000000; i+= 2){
        if(!auxciur[i]){
            nrprime[k] = i;
            k++;
        }
    }
}

int factorize(long long x){
    int l = 0,f = 0;
    while(x > 1){
        if(x%nrprime[l] == 0){
            divpB[f] = nrprime[l];
            f++;
            while(x%nrprime[l] == 0){
                x /= nrprime[l];
            }
        }
        if(nrprime[l]*nrprime[l] > x && x > 1){
            divpB[f] = x;
            f++;
            x = 1;
        }
        l++;
    }
    return f;
}

int main(){
    long long m,i,A,B,nrf,j,l,prod,nrpprod,sol;
    long long semn;
    fin>>m;
    ciur();
    for(i = 1; i <= m; i++){
        fin>>A>>B;
        sol = A;
        nrf = factorize(B);
        for(j = 1; j < (1<<nrf); j++){
            prod = 1;
            nrpprod = 0;
            for(l = 0; l < nrf; l++){
                if((1<<l)&j){
                    prod = prod*divpB[l];
                    nrpprod++;
                }
            }
            if(nrpprod%2){
                semn = -1;
            }else{
                semn = 1;
            }
            sol += semn*(A/prod);
        }
        fout<<sol<<endl;
    }
    return 0;
}