#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int t, a, b, n, nrc, rez, p, nrp, i, j;
int prime[100005], v[105];
bool  ciur[1000005];
int main() {
    fin >> t;
    for (i=2;i<=1000005;i++){
        if (ciur[i] == 0){
            prime[++nrp] = i;
            for (j=i+i;j<1000005;j+=i)
                ciur[j] = true;
        }
    }
    while(t--){
        fin >> a >> b;
        n = 0;
        i = 1;
        while(b > 1 && prime[i] * prime[i] <= b){
            if (b % prime[i] == 0){
                v[++n] = prime[i];
                while(b % prime[i] == 0){
                    b /= prime[i];
                }
            }
            i++;
        }
        if (b > 1)
            v[++n] = b;
        rez = a;
        for (i=1;i<(1LL<<n);i++){
            nrc = 0;
            p = 1;
            for (j=0;j<n;j++){
                if (i & (1LL<<j)){
                    nrc ++;
                    p = p * v[j+1];
                }
            }
            if (nrc % 2 == 1)
                rez = rez - a/p;
            else
                rez = rez + a/p;
        }
        fout << rez << '\n';
    }
    return 0;
}