#include <fstream>

#define MAX 1000001

using namespace std;

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

int div[8000], fact[30];
bool ciur[MAX];

void gen(){
	for(int i = 2; i*i < MAX; i++){
		if(!ciur[i]){
			for(int j = 2*i; j < MAX; j += i)
				ciur[j] = 1;
			div[++div[0]] = i;
		}
	}
}

int main(){
	int m, cop;
	int i, j, k, ind = 0;
	long long a, b;

	gen();

	in>>m;
	for(i = 0; i < m; i++){
		in>>a>>b;

		cop = b;
		ind = 0;

		k = 1;

		while(b > 1){
			if(b%div[k] == 0){
				b /= div[k];
				fact[ind++] = div[k];
				while(b%div[k] == 0) b /= div[k];
			}

			if(div[k]*div[k] > b && b > 1){
				fact[ind++] = b;
				b = 1;
			}
			++k;
		}

		long long sol = a;

		for(k = 1; k < (1<<ind); k++){
			char semn = 1;
			long long prod = 1;
			for(j = 0; j < ind; j++){
				if((k >> j) & 1){
					prod *= 1LL*fact[j];
					semn = -semn;
				}
			}

			sol += (1LL * (int)semn * a/prod);
		}

		out<<sol<<'\n';
	}
	return 0;
}