#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
vector<int> d;
vector<int> prim;

bool p[1000001];
int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    for(int i = 2; i <= 1000000; ++i) {
      if(!p[i]) {
         prim.push_back(i);
         for(int j = 2*i; j <= 1000000; j += i)
            p[j] = 1;
      }
    }
    long long m, a, b, p;
    cin >> m;
    for(int i = 1; i <= m; ++i) {
      cin >> a >> b;
      long long nr = 0;
      long long lim = sqrt(b);
      while(b > 1) {
         if(b % prim[nr] == 0) d.push_back(prim[nr]);
         while(b % prim[nr] == 0) {
            b = b/prim[nr];
         }
         if(prim[nr] > lim && b > 1) {
            d.push_back(b);
            b = 1;
         }
         ++nr;
      }
      long long sol = 0;
      for(int j = 1; j < (1 << d.size()); ++j) {
        nr = 0, p = 1;
        for(int k = 0; k < d.size(); ++k)
            if ((1 << k) & j) {
                p = p * d[k];
                ++nr;
            }
        if (nr % 2) nr = 1;
        else nr = -1;
        sol = sol + nr * a / p;
      }
      cout << a - sol << '\n';
      d.clear();
    }
    return 0;
}