#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

const int DIM = 1e6 + 1;
const int MX = 13;

bool ciur[DIM];
int pr[DIM];
int now[MX], z;
ll res, a;

void bkt( int pos, ll prod = 1, int cnt = 0 ) {
  if ( pos == z + 1 ) {
	if ( cnt == 0 ) return;
	if ( cnt & 1 ) {
	  res += a / prod;
	} else {
	  res -= a / prod;
	}
	return;
  }
  bkt(pos + 1, prod, cnt);
  bkt(pos + 1, prod * now[pos], cnt + 1);
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int t, idx = 0;
  ll b;

  fin >> t;
  for ( int d = 2; d < DIM; ++d ) {
	if ( !ciur[d] ) {
	  pr[++idx] = d;
	  for ( int i = d + d; i <= DIM; i += d ) {
		ciur[i] = 1;
	  }
	}
  }
  pr[++idx] = DIM;
  while ( t-- ) {
	fin >> a >> b;
	int i = 1;
	res = z = 0;
	while ( (ll)pr[i] * pr[i] <= b ) {
	  int e = 0;
	  while ( b % pr[i] == 0 ) {
		b /= pr[i];
	    ++e;
	  }
      if ( e ) {
        now[++z] = pr[i];
	  }
	  ++i;
	}
	if ( b > 1 ) {
	  now[++z] = b;
	}
	bkt(1);
	fout << a - res << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}