#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define int long long
int a, b;

signed main()
{
    int tt; fin >> tt;
    while(tt--) {
        fin >> a >> b;
        vector<int> div;
        int d = 2;
        while(b > 1) {
            if(b % d == 0) {
                div.push_back(d);
                while(b % d == 0) b /= d;
            }
            d++;
            if(d * d > b) d = b;
        }
        int cntNeprime = 0, lung = div.size();
        for(int mask=1; mask < (1 << lung); mask++) {
            int prod = 1, cntBiti = 0;
            for(int i=0; i<lung; i++)
                if(mask & (1 << i)) prod *= div[i], cntBiti++;
            if(cntBiti % 2 == 1) cntNeprime += (a / prod);
            else cntNeprime -= (a / prod);
        }
        fout << a - cntNeprime << '\n';
    }

    return 0;
}