#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("pinex.in");
ofstream gg("pinex.out");
#define max 1000001
bitset<max>pp;
vector<long long>qq;

void ciu(){
	int i=2, l=(int)sqrt(max);
	while(i<=l){
		while(pp[i])i++;
		for(int j=i*i;j<max;j+=i)pp[j]=1;
		i++;
	}
	for(int i=2;i<max;i++)
	if(!pp[i])qq.push_back(i);
}

int k;
long long a, b, dd[20];
bool bb[20];

void dsc(long long n){
	int i=0, l=qq.size();
	k=0;
	while(n!=1 && i<l && qq[i]*qq[i]<=n){
		if(n%qq[i]==0){ 
			dd[k++]=qq[i];
			while(n%qq[i]==0)n/=qq[i];
		}
		i++;
	}
	if(n!=1) dd[k++]=n;
}

void clc(long long n){
	long long s=0, p=1;
	memset(bb,0,sizeof(bb));
	int i=0, w=0;
	while(bb[k]==0){
		i=0;
		while(bb[i]){ bb[i]=0; p/=dd[i]; w--; i++; }
		bb[i]=1; w++; p*=dd[i];
		if(bb[k]) break;
		if(w%2) s+=n/p; else s-=n/p;
	}
	gg << n-s << endl;
}

int main(){
	int t;
	ciu();
	ff >> t;
	while(t--){
		ff >> a >> b;
		dsc(b);
		clc(a);
	}
	return 0;
}