#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e6;

vector<long long> primes;
long long v[NMAX];
char c[NMAX + 10];

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

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int m;
    fin>>m;
    ciur();
    while( m -- ) {
      long long a, b;
      fin>>a>>b;
      long long nr = 0;
      for(auto it : primes){
        if(1LL * it * it > b)
          break;
        if(b % it == 0)
          v[nr ++] = it;
        while(b % it == 0)
          b /= it;
      }
      if(b > 1)
        v[nr ++] = b;

      long long lim = (1LL << nr) - 1;
      long long ans = a;
      for( long long i = 1; i <= lim; i ++ ) {
        long long div = 1;
        int sgn = 1;
        for( int j = 0; j < nr; j ++ ) {
          if( i & (1LL<<j) ) {
            sgn *= -1;
            div *= v[j];
          }
        }
        ans = ans + sgn * (a / div);
      }
      fout<<ans<<"\n";
    }
    return 0;
}