#include <fstream>
#include <math.h>
using namespace std;

char V[10000002];
int P[100000];

long long pd, A, B, s;
int T, rb, i, j, x, X[100], nd, p;

int main(){
	
	ifstream f("pinex.in");
	ofstream g("pinex.out");
	
	for (i=2;i<=1000000;i++) {
		if (V[i] == 0){
			P[++p] = i;
			for (j=i+i;j<=1000000;j+=i)
				V[j] = 1;
		}
	}
	f>>T;
	for (;T;T--) {
		f>>A>>B;
		s = 0;
		x = 0;
		rb = (int)sqrt(B*1.0);
		
		for (i=1;P[i]<=rb && B!=1;i++) {
			if (B%P[i] == 0) {
				X[++x] = P[i];
				while (B%P[i] == 0) {
					B/=P[i];
				}
			}
		}
		if (B!=1) {
			X[++x] = B;
		}

		for (i=1;i<(1<<x);i++) {
			pd = 1;
			nd = 0;
			for (j=0;j<x;j++)
				if ((i>>j)&1) {
					pd *= X[j+1];
					nd++;
				}
			if (nd%2 == 1)
				s += A/pd;
			else
				s -= A/pd;
			}
		
		g<<A-s<<"\n";
	}
	
	return 0;
}