#include <fstream>
#include <math.h>
#include <vector>

using namespace std;

const int MAXN = 1000000;

bool ciur[MAXN];
vector<int> prim;
long long divb[30];

int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    long long n, a, b;
    fin >> n;
    for(int i = 2; i < MAXN; ++i){
        if(!ciur[i]){
            prim.push_back(i);
            for(int j = 2 * i; j < MAXN; j += i)
                ciur[j] = 1;
        }
    }
    while(n){
        fin >> a >> b;
        long long t = 0, d = 0;
        while(b > 1){
            if(b % prim[d] == 0){
                divb[++t] = prim[d];
                while(b % prim[d] == 0)
                    b /= prim[d];
            }
            if(prim[d] > sqrt(b) && b > 1){
                divb[++t] = b;
                b = 1;
            }
            d++;
        }
        long long ans = a;
        for(int i = 1; i < (1 << t); ++i){
            long long nr = 0, prod = 1;
            for(int j = 0; j < t; ++j){
                if((1 << j) & i){
                    prod *= 1LL * divb[j + 1];
                    nr++;
                }
            }
            if(nr % 2) nr = -1;
            else nr = 1;
            ans += nr * a / prod;
        }
        fout << ans << "\n";
        n--;
    }
    return 0;
}