#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

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

int main() {
    int tt;
    fin >> tt;
    while(tt--) {
        long long a, b;
        fin >> a >> b;
        long long d=2;
        vector<long long> oszt;
        while(b>1) {
            if(b%d==0) {
                oszt.push_back(d);
                while(b%d==0) {
                    b/=d;
                }
            }
            if(d==2) {
                d++;
            } else {
                d+=2;
            }
            if(d*d>b && b>1) {
                oszt.push_back(b);
                b=1;
            }
        }

        int meret=oszt.size();
        long long ans=a;
        for(int i=1; i<(1 << meret); i++) {
            long long szor=1, cnt=0;
            for(int j=0; j<meret; j++) {
                if(i & (1 << j)) {
                    szor=szor*oszt[j];
                    cnt++;
                }
            }

            if(cnt%2==0) {
                cnt=1;
            } else {
                cnt=-1;
            }
            ans=ans+cnt*a/szor;
        }
        fout << ans << '\n';
    }

    return 0;
}