#include <iostream>
#include <fstream>
#include <vector>
#define nl '\n'

using namespace std;

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

const int VMAX = 1e6+1;
long long int a, b, ans;
long long int n;
bool prim[VMAX];
vector<long long int> pr, dvs;

void ciur()
{
    prim[0] = 1;
    prim[1] = 1;
    for (int i = 4; i < VMAX; i+=2)
        prim[i] = 1;
    for (int i = 3; i*i < VMAX; i+=2)
    {
        if (prim[i] == 0)
        {
            for (int j = i*i; j < VMAX; j+= 2*i)
                prim[j] = 1;
        }
    }
    for (int i = 2; i < VMAX; i++)
        if (!prim[i])
            pr.push_back(i);
    return;
}
void solve()
{
    dvs.clear();
    fin >> a >> b;
    for (int i = 0; i < pr.size(); i++)
    {
        int nr = pr[i];
        if (pr[i] > b)
            break;
        if (b % pr[i] == 0)
        {
            dvs.push_back(pr[i]);
            while (b % pr[i] == 0)
                b/=pr[i];
        }
    }
    if (b > 1)
        dvs.push_back(b);
    ans = 0;
    n = dvs.size();
    for (int i = 1; i < (1<<n); i++)
    {
        long long int cnt = 0;
        long long int p = 1;
        for (int j = 0; j < n; j++)
        {
            if (i&(1<<j))
            {
                cnt++;
                p*=dvs[j];
            }
        }
        if (cnt&1)
            ans+=a/p;
        else
            ans-=a/p;
    }
    fout << a-ans << nl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    fin >> t;
    ciur();
    while (t--)
    {
        solve();
    }
    return 0;
}