#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 1000000

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long t, a, b;
vector <long long> prim, fact;
bool c[Nmax+10];

void ciur()
{
    long long last=0;
    for (int i = 2; i*i < Nmax-4; i++)
        if (c[i] == 0)
        {
            last=i;
            prim.push_back(i);
            for (int j = i+i; j < Nmax-4; j+=i)
                c[j]=1;
        }
    for (int i = last*last+1; i <= Nmax; i++)
        if (c[i]==0) prim.push_back(i);
}

void solve()
{
    long long copie=b;
    fact.clear();
    auto it=prim.begin();
    while (copie!=1)
    {
        if (copie%(*it) == 0)
        {
            fact.push_back(*it);
            while (copie%(*it) == 0) copie/=(*it);
        }
        it++;
    }

    if (copie > 1) fact.push_back(copie);

    // for (auto k:fact)
      // cout << k << " ";
    // cout << '\n';

    long long sol=a, t=fact.size();
    for (int i = 1; i < (1<<t); i++)
    {
        long long nr=0, prod=1;
        for (int j = 0; j < t; j++)
        {
            if (i&(1<<j))
            {
                prod=1ll*prod*fact[j];
                nr++;
            }
        }
        if (nr%2) nr=-1;
        else nr=1;

        sol+=1ll*nr*a/prod;
    }

    g << sol << '\n';
}

int main()
{
    ciur();
    //for (auto i:prim) cout << i << '\n';
    f >> t;
    while (t--)
    {
        f >> a >> b;
        solve();
    }

    return 0;
}