#include <cstdio>
#include <bitset>
#include <vector>
 
#define Nmax 1005000
#define Lim 1000666
 
 
using namespace std;
bitset<Nmax> ciur;
vector<int> is_prime;
vector<long long> divi;
 
void precalc()
{
    is_prime.push_back(2);
    for(int i = 1; ((i<<1)|1) <= Lim; ++i)
        if(!ciur[(i<<1)|1])
        {
            is_prime.push_back((i<<1)|1);
            for(int j = 1; (((j<<1)|1) * ((i<<1)|1)) <= Lim; ++j)
                ciur[(((j<<1)|1) * ((i<<1)|1))] = 1;
        }
}
 
void get_divi(long long B)
{
    divi.clear();
    int i,prim = 1;
    for(i = 0; is_prime[i]*is_prime[i] <= B; ++i)
    {
        if(B % is_prime[i] == 0)
            divi.push_back(is_prime[i]);
        while(B % is_prime[i] == 0)
            B /= is_prime[i];
    }
    if(B > 1)
        divi.push_back(B);
}
 
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
 
    precalc();
    int T;
    scanf("%d",&T);
 
    long long A,B,rez;
    while(T--)
    {
        scanf("%lld%lld\n",&A,&B);
        get_divi(B);
        rez = 0;
        long long crt = 1;
        int lf = (1<<divi.size()) - 1,cnt;
        for(int mask = 0; mask <= lf; ++mask)
        {
            crt = 1;
            cnt = 0;
            for(int i = 0; i < divi.size(); ++i)
                if(mask & (1<<i))
                {
                    crt *= divi[i];
                    ++cnt;
                }
            if(cnt & 1)
                rez -= A/crt;
            else
                rez += A/crt;
        }
        printf("%lld\n",rez);
    }
 
    return 0;
}