#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#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()
{
    for (int i = 2; i < Nmax-4; i++)
        if (c[i] == 0)
        {
            prim.push_back(i);
            for (int j = 2*i; j < Nmax-4; j+=i)
                c[j]=1;
        }
}

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

    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;
}