#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int NMAX = 1e6 + 1;

vector<long long> primes;

char c[NMAX + 1];

void ciur() {
  for( int i = 2; i * i <= NMAX; i ++ ) {
    if( c[i] == 0 ) {
      for( int d = i * i; d <= NMAX; d = d + i )
        c[d] = 1;
    }
  }
  for( int i = 2; i <= NMAX; i ++ )
    if( c[i] == 0 )
      primes.push_back(i);
}

int main() {
    int m;
    fin>>m;
    ciur();
    while( m -- ) {
      long long a, b;
      fin>>a>>b;
      vector<long long> factori;
      for( int i = 0; primes[i] * primes[i] <= b; i ++ ) {
        if( b % primes[i] == 0 )
          factori.push_back(primes[i]);
        while( b % primes[i] == 0 ) {
          b /= primes[i];
        }
      }
      if( b > 2 )
        factori.push_back(b);

      long long lim = (1LL << factori.size()) - 1;
      long long ans = a;
      for( long long i = 1; i <= lim; i ++ ) {
        long long div = 1;
        int biti = 0;
        for( int j = 0; j < factori.size(); j ++ ) {
          if( i & (1LL<<j) ) {
            div *= factori[j];
            biti ++;
          }
        }
        if( biti % 2 == 0 )
          ans = ans + (a / div);
        else
          ans = ans - (a / div);
      }
      fout<<ans<<"\n";
    }
    return 0;
}