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

vector <int> D;
bool E[MAXN];

int main(){
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	int t;
	cin>>t;
	while(t--){
		D.clear();
		ll a,b;
		int d=2;
		cin>>a>>b;
		while(b>1){
			if(b%d==0){
				D.push_back(d);
				while(b%d==0)b/=d;
			}
			if(b%d==0 && d>sqrt(b) && b>1){
				D.push_back(d);
				b=1;
			}
			if(d==2)d++;
			else d+=2;
		}
		ll s=0,l=(1<<D.size()),lj=D.size(),prod=1;
		//for(int i=0;i<D.size();i++)cout<<D[i]<<' ';
		//cout<<'\n';
		for(int i=1;i<l;i++){
			int c=0;
			prod=1;
			for(int j=0;j<lj;j++){
				if((1<<j)&i){
					prod*=D[j];
					c++;
				}
			}
			if(c%2)prod=-prod;
			s+=a/prod;
		}
		cout<<s<<'\n';	
	}
	return 0;
}