#include <bits/stdc++.h>

using namespace std;

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

long long m,a,b;
vector<int> divp;

void divprim(int nr){
    divp.clear();
    long long p = 3;
    if(nr%2==0){
        divp.push_back(2);
        while(nr%2==0){
            nr/=2;
        }
    }
    while(nr!=1){
        if(nr%p == 0){
            divp.push_back(p);
            while(nr%p == 0){
                nr/=p;
            }
        }
        p+=2;
    }
}

int main() {
    long long SOL,i,j,k,semn,prodaux;
    fin>>m;
    for(i = 1; i <= m; i++){
        fin>>a>>b;
        divprim(b);
        SOL = a;
        for(j = 1; j < (1<<divp.size()); j++){
            semn=1;
            prodaux = 1;
            for(k = 0; k < divp.size(); k++){
                if(j&(1<<k)){
                    prodaux *= divp[k];
                    semn = -semn;
                }
            }
            SOL += semn*(a/prodaux);
        }
        fout<<SOL<<'\n';
    }
    return 0;
}