#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define int long long
using namespace std;

ifstream cin ("pinex.in");
ofstream cout ("pinex.out");

vector<int> prime_factors;

void solve() {
    int a, b;
    cin>>a>>b;
    prime_factors.clear();
    int temp=b;
    for (int i=2; i*i<=temp; i++) {
        if (temp%i==0) {
            prime_factors.push_back(i);
            while (temp%i==0) {
                temp/=i;
            }
        }
    }
    if (temp>1) {
        prime_factors.push_back(temp);
    }
    int k=prime_factors.size();
    int non_coprime=0;
    for (int mask=1; mask<(1<<k); mask++) {
        int prod=1;
        int bits_cnt=0;
        for (int i=0; i<k; i++) {
            if (mask&(1<<i)) {
                bits_cnt++;
                prod*=prime_factors[i];
            }
        }
        if (bits_cnt%2==1) {
            non_coprime+=a/prod;
        } else {
            non_coprime-=a/prod;
        }
    }
    cout<<a-non_coprime<<"\n";
}

signed main() {
    int m;
    cin>>m;
    while (m--) {
        solve();
    }
}