#include <bits/stdc++.h>

using namespace std;

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

long long p, prim[100];
long long n, m, x, sol, prd, cnt;

void divd(long long d){
    long long e = 0;
    while(m % d == 0){
        e++;
        m /= d;
    }
    if(e != 0)
        prim[p++] = d;
}

signed main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    long long teste;
    fin>>teste;
    while(teste--){
        fin>>n>>x;
        sol = 0;

        p = 0;
        m = x;
        divd(2);
        divd(3);
        for(long long i=5; i<=m/i; i+=6)
            divd(i), divd(i+2);
        if(m > 1)
            divd(m);

        for(long long mask=1; mask < (1<<p); mask++){
            prd = 1;
            cnt = 0;
            for(long long i=0; i < p; i++)
                if(mask & (1<<i)){
                    prd *= prim[i];
                    cnt++;
                }
            if(cnt&1)
                sol += n / prd;
            else
                sol -= n / prd;
        }
        fout<<n-sol<<"\n";
    }
    return 0;
}