#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long f[12];
int e = 0;
long long a;
void desc(long long x){
    long long d = 3;
    if(x % 2 == 0){
        f[++e] = 2;
        while(x % 2 == 0) x /= 2;
    }
    while(x > 1){
        if(x % d == 0){
            f[++e] = d;
            while(x % d == 0) x /= d;
        }
        if(d * d > x) d = x;
        else d += 2;
    }
}
long long backt(){
    long long s = 0,p,k;
    for(long long i = 1; i < (1LL << e); i++){
        p = 1;
        k = 0;
        for(int j = 0; j < e; j++){
            if(i & (1LL << j)){
                p *= f[j + 1];
                k++;
            }
        }
        if(k % 2 == 0) s -= a / p;
        else s += a / p;
    }
    return s;
}
int main()
{
    int n,i,j;
    long long b;
    fin >> n;
    for(i = 1; i <= n; i++){
        fin >> a >> b;
        e = 0;
        desc(b);
        fout << a - backt() << "\n";
    }
    return 0;
}