#include <map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cfloat>
#include <numeric>

using namespace std;

const int    oo  = 0x3f3f3f3f;
const double eps = 1e-9;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(c) int ((c).size())
#define all(c) (c).begin(), (c).end()
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define FORIT(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define mp make_pair
#define pb push_back
#define MAX_N 1 << 20

ll A, B;
unsigned char p[MAX_N];
int primes[100000], K;

int fact[1 << 7];

void sieve () {
     for (int i = 2; i * i <= MAX_N; ++i) if (p[i] != 1)
         for (int j = i * i; j < MAX_N; j += i) p[j] = 1;
     K = 0;
     FOR (i, 2, MAX_N) if (p[i] != 1) primes[K++] = i;
}

int main () {
    freopen ("pinex.in", "r", stdin);
    freopen ("pinex.out", "w", stdout);
    
    sieve();
    
    int tests;
    scanf ("%d", &tests);
    while (tests--) {
          scanf ("%lld %lld", &A, &B);
          
          int k = 0;
          FOR (i, 0, K) {
              if (B % primes[i]) continue;
              
              fact[k++] = primes[i];
              while (B % primes[i] == 0) B /= primes[i];
              
              if (B == 1) break;
          }
          if (B > 1) fact[k++] = B;
          
          ll ANSWER = A;
          
          FOR (p, 1, (1 << k)) {
              ll nums = 0, product = 1;
              
              FOR (i, 0, k) if (p&(1 << i)) {
                  product = product * fact[i];
                  
                  ++nums;
              }
              ANSWER += (A / product) * ((nums & 1) ? -1 : 1);
          }
          
          printf ("%lld\n", ANSWER);
    }

    return 0;
}