#include <bits/stdc++.h>
#define maxN 102
#define maxV 2000003
#define ll long long
using namespace std;
int n, m;
ll a, b, sol, d[maxN];
bool w[maxV];
int p[maxV / 9];
void primes()
{
   int i, j, ok = 0;
   w[1] = 1;
   for (i = 2; i < maxV; ++ i)
      if (!w[i])
      {p[++ p[0]] = i;
      if (i * i > maxV)
         ok = 1;
      if (!ok)
      for (j = i * i; j < maxV; j += i)
          w[j] = 1;
    }
  }
void desc(ll x)
{
   int i;
   sol = a;
   d[0] = 0;
   for (i = 1; p[i] * p[i] * 1LL <= x; ++ i)
       if (x % p[i] == 0)
    {
        while (x % p[i] == 0)
              x /= p[i];
        d[++ d[0]] = p[i];
    }
    if (x != 1LL)
    {
        d[++ d[0]] = x;
    }
}
void solve()
{
   int i, j, nb1;
   ll p;
   desc(b);
   for (i = 1; i < (1 << d[0]); ++ i)
   {
       nb1 = 0;
       p = 1LL;
       for (j = 0; j < d[0]; ++ j)
           if (i & (1 << j))
        {
            ++ nb1;
            p *= d[j + 1];
        }
        if (nb1 % 2)
           sol -= (a / p);
        else
           sol += (a / p);
   }
}
void write()
{
   printf("%lld\n", sol);
}
void rsw()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &m);
    primes();
    while (m --)
    {
        scanf("%lld %lld", &a, &b);
        solve();
        write();
    }
}
int main()
{
    rsw();
    return 0;
}