#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define ll long long
ll t, a, b, n, nrc, ans, p, nr, i, j;
ll prime[100005], v[105];
bool ciur[1000005];
int main() {
    fin >> t;
    for (i=2;i<=1000005;i++){
        if (ciur[i] == 0){
            prime[++nr] = 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;
        ans = 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)
                ans = ans - a/p;
            else
                ans = ans + a/p;
        }
        fout << ans << '\n';
    }
    return 0;
}