#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 1000000
#define ll long long

int m, i, nprim[MAX], div[100];
bool prim[MAX];
ll a, b;

void ciur();
void pinex(ll a, ll b);

int main(){
	freopen("pinex.in", "r", stdin);
	freopen("pinex.out", "w", stdout);
	scanf("%d", &m);
	ciur();
	for(i = 0; i < m; i++){
		scanf("%lld%lld", &a, &b);
		pinex(a, b);
	}

	return 0;
}

void ciur(){
	int j;
	memset(prim, true, MAX);
	for(i = 2; i < MAX; i++)
		if(prim[i]){
			for(j = 2 * i; j < MAX; j += i)
				prim[j] = false;
			nprim[++nprim[0]] = i;
		}
}

void pinex(ll a, ll b){
	int nr = 0, i, j;
	for(i = 1; i < nprim[0]; i++){
		if(b % nprim[i] == 0){
			div[++nr] = nprim[i];
			while(b % nprim[i] == 0)
				b /= nprim[i];
		}
		if(nprim[i] > sqrt(b) && b > 1){
			div[++nr] = b;
			break;
		}
	}

	ll solution = a;
	for(i = 1; i < (1<<nr); i++){
		ll p = 1, t = 0;
		for(j = 0; j < nr; j++)
			if((1<<j) & i){
				p *= (ll)div[j + 1];
				t++;
			}

		if(t % 2)
			t = -1;
		else
			t = 1;

		solution += (ll)t * a / p;
	}

	printf("%lld\n", solution);
}