#include <fstream>
#include <cstring>
#include <bitset>
#define DIM 1000010
using namespace std;

ifstream fin ("pinex.in" );
ofstream fout("pinex.out");

int N, M, i, j, K, ok, minim;
int P[DIM/10], T[DIM], U;
bitset <DIM> F, Back; int Q;
long long A, B, nr, val, sumtot, val2;

void Sieve(){
	P[++K] = 2;
	F[0] = 1;
	F[1] = 1;
	int i;
	for(i = 4; i < DIM; i += 2)
		F[i] = 1;
	for(i = 3; i < DIM; i += 2){
		if(F[i] == 0){
			P[++K] = i;
			for(j = i + i + i; j < DIM; j += i + i)
				F[j] = 1;
		}
	}
	return;
}

void Descompose(long long val){
	int i = 1;
	for(i = 1; i <= U; i ++)
		T[i] = 0;
    U = 0;
    long long val2 = val;
	for(i = 1; P[i] * 1LL * P[i] <= val2 && val != 1; i ++){
		if(val % P[i] == 0){
			T[++U] = P[i];
			while(val % P[i] == 0)
				val /= P[i];
		}
	}
	if(val != 1)
		T[++U] = val;
	return;
}

void BackTrack(){
	for(i = 0; i <= U; i ++)
		Back[i] = 0;
	nr = 0, val = 0;
	sumtot = 0;
	while(Back[0] == 0){
		i = U;
		while(Back[i] == 1)
			Back[i--] = 0;
		Back[i] = 1;
		if(Back[0] == 1)
                break;
		nr = 0;
		val = 1;
		for(i = 1; i <= U; i ++)
			if(Back[i] == 1){
				val *= T[i];
				nr ++;
			}
		if(nr % 2 == 1)
			sumtot += (A / val);
		else
			sumtot -= (A / val);
	}
	fout << A - sumtot << "\n";
	return;
}

void CodeExpert(){
	fin >> Q;
	for(Q = Q; Q >= 1; Q --){
		fin >> A >> B;
		Descompose(B);
		BackTrack();
	}
	return;
}

int main(){
	Sieve();
	CodeExpert();
	return 0;
}