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

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

void Build(vector<int> &v, int a, int b, vector<bool>Ciur){
    
    for(int i=2;i<=b;i++){
        if(!Ciur[i]){
            continue;
        }
        
        if(b%i==0){
            v.push_back(i);
        }
    }
    
    return;
}

long long int Pinex(vector<int> v, int a, int b){
    
    unsigned short Bitmask=1;
    long long int sum=0, cnt=0;
    int prod;
    //out<<v.size()<<"\n";
        for(; Bitmask < 1ll << v.size() ;Bitmask++){
            prod=1;
            cnt=0;
        for(int i=0;i<16;i++){
            if(Bitmask & (1 << i)){
                prod*=v[i];
                cnt++;
            }            
        }
        if(cnt%2)
        sum-=(a/prod);
        
        else sum+=a/prod;
    }

    return sum;
}

int main(){
    
    int t;
    in>>t;
    
    vector<bool>Ciur(1e6, 1);
    
    for(int i=2;i<1e3;i++){
        if(Ciur[i]){
            for(int j=2;j*i<1e6;j++){
                Ciur[i*j]=0;
            }
        }
    }
    
    
    int a, b;
    vector<int> v; // numerele prime cu care se divide b
    
    // for(int i=0;i<1e6;i++)
    // out<<Ciur[i]<<" ";
    
    for(int k=0;k<t;k++){
        
        v.clear();
        in>>a>>b;
        Build(v, a, b, Ciur);
        // for(int i=0;i<v.size();i++){
        //     out<<v[i]<<" ";
        // }
        // out<<"\n";
        out<<a+Pinex(v, a, b)<<"\n";
    }
    
}