#include <fstream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

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

const int VMAX=1e6;

long long n, A, B;
bool ciur[VMAX+5];
vector<int> primes;

void generate_primes(){
    for(int i=2;i<=VMAX;i++){
        ciur[i]=true;
    }
    for(int i=2;i<=VMAX;i++){
        if(ciur[i]){
            for(int j=2*i;j<=VMAX;j+=i){
                ciur[j]=false;
            }
            primes.push_back(i);
        }
    }
}

vector<long long> get_primes(long long n){
    vector<long long> ans;
    int d=0;
    while(d<primes.size()&&primes[d]*primes[d]<=n){
        if(n%primes[d]==0){
            ans.push_back(primes[d]);
            while(n%primes[d]==0){
                n=n/primes[d];
            }
        }
        d++;
    }
    if(n>1){
        ans.push_back(n);
    }
    return ans;
}

long long query(long long A, long long B){
    vector<long long> primes=get_primes(B);
    int x=primes.size();
    long long ans=0;
    for(int i=0;i<(1<<x);i++){
        long long p=1;
        int cnt=0;
        for(int j=0;j<x;j++){
            if(i&(1<<j)){
                p=p*primes[j];
                cnt++;
            }
        }
        if(cnt%2==0){
            ans+=A/p;
        }
        else{
            ans-=A/p;
        }
    }
    return ans;
}

int main(){
    generate_primes();
    cin>>n;
    while(n--){
        cin>>A>>B;
        cout<<query(A, B)<<'\n';
    }
}