#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int LMAX = 100005;
const int INF = 0x3f3f3f3f;
const ll MOD = 1000000007;

//Ai --> nr de nr mai mici sau egale cu A care sunt divizibile cu i
//|A1 U A2 U ... An| = |A1| + ... - |A1 int A2| + ...

int main() {
    int m;
    ll a, b;
    fin>>m;
    while (m--) {
        fin>>a>>b;
        vector<int> prime;
        ll p;
        p = 2;
        while (p*p <= b) {
            if (b%p == 0) {
                prime.push_back(p);
                while (b%p == 0) {
                    b = b/p;
                }
            }
            p++;
        }
        if (b != 1) prime.push_back(b);
        ll s = prime.size(), ans = 0;
        for (ll mask = 1; mask < (1<<s); mask++) {
            ll divi = 1;
            bool sign = 1;
            for (ll i = 0; (1<<i) <= mask; i++) {
                if (mask&(1<<i)) {
                    divi = divi*prime[i];
                    sign = 1 - sign;
                }
            }
            if (sign) {
                ans = ans - a/divi;
            }
            else {
                ans = ans + a/divi;
            }
        }
        fout<<a - ans<<"\n";
    }



    fin.close();
    fout.close();
    return 0;
}