#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];
long long sum, ans, d;

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

int pinex()
{
    int i;
    d = 2;
    ans = 0;
    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(1, i, 1);
        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;
}