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

ll D[MAXN];

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