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

using namespace std;

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

int t, vf = 0;
long long a, b, divizori[DM];

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

int pinex()
{
    long long d = 2, ans = 0, sum, i;
    vf = 0;
    while(d * d <= b)
    {
        if(b % d == 0)
        {
            divizori[++vf] = d;
            while(b % d == 0)
                b /= d;
        }
        d++;
    }
    if(b > 1)
        divizori[++vf] = b;
    for(i = 1; i <= vf; i++)
    {
        sum = 0;
        bkt(a, 1, i, 1, sum);
        if(i % 2 == 1)
            ans += sum;
        else
            ans -= sum;
    }

    return a - ans;
}

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