#include <stdio.h>
#include <string.h>
#define MAXRAD 1000010

int P[80000];
bool prim[MAXRAD];
long long A, B, sum;
int T, D[100];


inline void factori()
{
	memset(prim, true, sizeof(prim));
	P[++P[0]] = 2;
	for (int i=3; i<MAXRAD; i+=2)
		if (prim[i]){
			P[++P[0]] = i;
			for (int j=3*i; j<MAXRAD; j+=(i<<1))
				prim[j] = false;
		}
}

inline void solve()
{
	scanf("%lld %lld",&A, &B);
	D[0] = 0; sum = 0;
	for (int i=1; i<P[0] && B/P[i] >= P[i]; i++)
		if (B%P[i] == 0){
			D[++D[0]] = P[i];
			while (B%P[i] == 0)
				B/=P[i];
		}
	if (B!=1) D[++D[0]] = (int)B;
/*
	for (int i=1; i<(1<<D[0]); i++){
		int nr = 0;
		long long prod = 1;
		for (int j=0; j<D[0]; j++)
			if (i & (1<<j)){
				prod =1LL * prod * D[j+1];
				nr++;
			}
		if (nr&1)
			sum -= (A/prod);
		else
			sum += (A/prod);
	}*/
	printf("%lld\n",A+sum);
}

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	factori();
	for (scanf("%d",&T); T; T--)
		solve();
	return 0;
}