#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define int long long
const int DIM = 1e6;
bitset <DIM>ciur;
vector<int> prime;

inline void prelucru() {
    ciur[0] = ciur[1] = 1;
    for(int i=2; i*i<=DIM; i++)
        if(!ciur[i])
            for(int j=i*i; j<=DIM; j+=i) ciur[j] = 1;
    for(int i=2; i<=DIM; i++)
        if(!ciur[i]) prime.push_back(i);
}

inline int solve(int a, int b) {
    int d = 0;
    vector<int> v;
    while(b > 1) {
        if(b % prime[d] == 0) {
            v.push_back(prime[d]);
            while(b % prime[d] == 0) b /= prime[d];
        }
        d++;
        if(prime[d] * prime[d] > b && b > 1) {
            v.push_back(b);
            break;
        }
    }
    int n = v.size(), rez = 0;
    for(int mask=1; mask<(1 << n); mask++) {
        int p = 1, cnt = 0;
        for(int i=0; i<n; i++)
            if(mask & (1 << i)) p = 1LL * p * v[i], cnt++;
        int sgn = 1;
        if(cnt % 2 == 0) sgn = -1;
        rez += (1LL * sgn * (a / p));
    }
    return a - rez;
}

signed main()
{
    prelucru();
    int tt; fin >> tt;
    while(tt--) {
        int a, b; fin >> a >> b;
        fout << solve(a, b) << '\n';
    }

    return 0;
}