#include <bits/stdc++.h>
#define DM 1000005
#define pb push_back

using namespace std;

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

int t, vf = 0, semn;
long long a, b, divizori[DM];
long long ans, d;
bool preciur[DM];
vector <int> ciur;

void initCiur()
{
    int i, j;
    for(i = 2; i <= DM; i++)
    {
        if(!preciur[i])
        {
            ciur.push_back(i);
            for(j = i + i; j <= DM; j += i)
                preciur[j] = true;
        }
    }
}

void bkt(int inceput, int nr, long long k)
{
    if(!nr)
    {
        ans += 1LL * semn * (a / k);
        return;
    }
    int i;
    for(i = inceput; i <= vf; i++)
        bkt(i + 1, nr - 1, k * divizori[i]);
}

int pinex()
{
    int i;
    ans = 0;
    vf = 0;
    for(i = 0; i < ciur.size() && ciur[i] * ciur[i] <= b; i++)
    {
        if(b % ciur[i] == 0)
        {
            divizori[++vf] = ciur[i];
            while(b % ciur[i] == 0)
                b /= ciur[i];
        }
    }
    if(b > 1)
        divizori[++vf] = b;
    for(i = 1; i <= vf; i++)
    {
        if(i % 2 == 1)
            semn = 1;
        else
            semn = -1;
        bkt(1, i, 1);
    }

    return a - ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    initCiur();
    fin >> t;
    for(; t; t--)
    {
        fin >> a >> b;
        fout << pinex() << '\n';
    }
    return 0;
}