#include <bits/stdc++.h>
#define int long long
using namespace std;

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

const int dim=1e6+9;

vector<int>prime;
bool ciur[dim];
void Eratosthenes(int MAX){
    ciur[0]=ciur[1]=1;
    for(int i=4;i<=MAX;i+=2){
        ciur[i]=1;
    }
    for(int i=3;i*i<=MAX;i+=2){
        for(int j=i*i;j<=MAX;j+=i){
            ciur[j]=1;
        }
    }
    for(int i=2;i<=MAX;i++){
        if(!ciur[i]){
            prime.push_back(i);
        }
    }
}

vector<int>fact;

void solve(){
    int A,B;
        fin>>A>>B;
    for(int it:prime){
        if(B%it==0){
            fact.push_back(it);
            while(B%it==0){
                B/=it;
            }
        }
        if(it*it>B&&B>1){
            fact.push_back(B);
            B=1;
        }
        if(B==1){
            break;
        }
    }
    int ans=A;
    int t=fact.size();
    for(int i=1;i<(1<<t);i++){
        int nr=0,prod=1;
        for(int j=0;j<t;j++){
            if((1<<j)&i){
                prod*=fact[j];
                nr++;
            }
        }
        ans+=(nr%2==1)? -A/prod : A/prod;
    }
        fout<<ans;
    fact.clear();
}

signed main(){
    Eratosthenes(1e6);
    int t=1;
        fin>>t;
    while(t--){
        solve();
        fout<<'\n';
    }
}