using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "pinex";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int valMAX = 1e6;

bool prime[valMAX + 1];
vector<int> primes;

void genPrimes()
{
   memset(prime, 1, valMAX + 1);
   prime[0] = prime[1] = 0;

   for (int i = 2; i*i <= valMAX; ++i)
      if (prime[i])
         for (int j = i*i; j <= valMAX; j += i)
            prime[j] = 0;
   
   for (int x = 2; x <= valMAX; ++x)
      if (prime[x])
         primes.pb(x);
}

int main()
{
   genPrimes();

   int m;
   cin >> m;
   while (m--)
   {
      ll a, b;
      cin >> a >> b;

      vector<int> divi;
      
      for (int d : primes)
         if (d > b)
            break;
         else if (b % d == 0)
         {
            divi.pb(d);
            for (; b%d == 0; b /= d);
         }
      if (b != 1)
         divi.pb(b);
      
      
      ll ans = a;
      for (int x = 1; x < (1 << divi.size()); ++x)
      {
         ll nr = 1;
         for (int j = 0; j < divi.size(); ++j)
            if (x & 1<<j)
               nr *= divi[j];
         
         if (__builtin_popcount(x) % 2 == 1)
            ans -= a / nr;
         else
            ans += a / nr;
      }

      cout << ans << '\n';
   }
}