#include <cstdio>
#include <bitset>
#include <vector>

#define crmax 1000005

using namespace std;
bitset<crmax> ciur;
vector<int> isprime;

void precalc()
{
    isprime.push_back(2);
    for(int i = 1; ((i<<1)|1) <= crmax - 2; ++i)
        if(ciur[((i<<1)|1)] == 0)
        {
            isprime.push_back(((i<<1)|1));
            for(int j = 1; ((i<<1)|1)*((j<<1)|1) <= crmax - 2; ++j)
                ciur[((i<<1)|1)*((j<<1)|1)] = 1;
        }
}
int N;
long long A,B;

long long calc(int A,int B)
{
    vector<int> v;
    for(int i = 0; isprime[i]*isprime[i] <= B; ++i )
    {
        if(B % isprime[i] == 0)
            v.push_back(isprime[i]);
        while( B % isprime[i] == 0)
            B /= isprime[i];
    }
    if(B > 1)
        v.push_back(B);
    int maxim = (1<<v.size())-1,nr = v.size()-1;
    long long total = 0;
    for(int mask = 1; mask <= maxim; ++mask)
    {
        long long crt = 1;
        int cate = 0;
        for(int i = 0; i <= nr; ++i)
            if(mask & (1<<i)) crt *= v[i],++cate;
        if(cate & 1)
            total += A / crt;
        else
            total -= A / crt;
    }
    return total;
}

void solve()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; ++i)
    {
        scanf("%lld%lld",&A,&B);
        printf("%lld\n",A - calc(A,B));
    }
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    precalc();
    solve();

    return 0;
}