#include<stdio.h>
#include<math.h>

#include<iostream>
#include<fstream>

#include<vector>
using namespace std;

#define MAXPRIME 1000000

int M;
long long A,B;

bool notprimes[MAXPRIME+1];
vector<int> primes;
vector<int> divB;

void computeprimes(){
	for(int i=2;i<=MAXPRIME;i++){
		if(notprimes[i]==false){
			primes.push_back(i);
			for(int j=2*i;j<=MAXPRIME;j+=i)
				notprimes[j]=true;
		}
	}
}

int n;

long long nk;

void combinari(int k,vector<int> & X,int i){
	if(i==k){
		long long prod=1;
		for(int j=0;j<k;j++)
			prod*=(long long)divB[X[j]];
		nk+=(A/prod);
		return;
	}
	int start=0;
	if(i>0) 
		start=X[i-1]+1; 
	for(int j=start;j<n;j++){
		X[i]=j; 
		combinari(k,X,i+1);
	}
}

long long computeint(int k){
	nk=0;
	vector<int> X(k); 
	combinari(k,X,0);
	return nk;
}

int main(){
	
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);

	scanf("%d",&M);

	computeprimes();
	int l=primes.size();

	long long nb;

	for(int i=0;i<M;i++){
		scanf("%lld %lld", &A, &B);
		nb=0;
		divB.clear();

		for(int i=0;i<l;i++){
			if(primes[i]>sqrt((double)B))
				break;
			if(B%primes[i]==0){
				divB.push_back(primes[i]);
				while(B%primes[i]==0){
					B=B/primes[i];
				}
			}
		}

		if(B>1){
			divB.push_back(B);	
		}

		n=divB.size();
		
		int semn=1;
		for(int k=1;k<=n;k++){
			if(semn==1)
				nb+=computeint(k);
			else
				nb-=computeint(k);
			semn*=-1;
		}
				
		printf("%lld\n",A-nb);
	}

	return 0;
}