#include <bits/stdc++.h>

using namespace std;
int d,t;
bool prim[1000005];
int fprim[80000];
int fact[100];
void sieve() {

	for (int i = 2; i < 1000000; i++)
		if (!prim[i]) {
			for (int j = 2 * i; j < 1000000; j += i)
				prim[j] = 1;
			fprim[++fprim[0]] = i;
		}
}
void desc (int B)
{
  d=0,t=0;
  while (B > 1)
  {
    d++;
    if (B % fprim[d] == 0)
    {
      fact[++t] = fprim[d];
      while (B % fprim[d] == 0)
        B /= fprim[d];
    }

    if (fprim[d] > sqrt(B) && B > 1)
    {
      fact[++t] = B;
      B = 1;
    }
  }
}
int calc(int a, int b)
{
  desc(b);
  int sol = a;
  for (int i = 1; i < (1 << t); i++)
  {
    int nr = 0, prod = 1;
    for (int j = 0; j < t; j++)
      if ((1 << j) & i)
      {
        prod = 1LL * prod * fact[j + 1];
        nr++;
      }

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

    sol = sol + 1LL * nr * a / prod;
  }
  return sol;
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
  sieve();
  int n;
  scanf("%d",&n);
  for(int i=1; i<=n; ++i)
  {
      int a,b;
    scanf("%d %d",&a,&b);
    printf("%d\n",calc(a,b));
  }
  return 0;
}