#include <bits/stdc++.h>
#define ll long long
#define MAX_B 1000000
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector<int>prim;
ll M, A, B, fact[30];

void erato()
{
    vector<bool>marked(MAX_B/2+1);
    for(int i=1 ; ((i*i)<<1)+(i<<1)<=MAX_B ; i+=1)if(!marked[i]){
        for(int j=((i*i)<<1)+(i<<1) ; (j<<1)+1 <=MAX_B ; j+=(i<<1)+1)
            marked[j]=true;
    }
    prim.push_back(2);
    for(int i=1;(i<<1)+1<=MAX_B;i+=1)
        if(!marked[i])
            prim.push_back(2*i+1);
    return;
}

void solve()
{
    ll t = 0, d = 2;
    vector<int>::iterator it;
    for(it=prim.begin();B>1&&it!=prim.end();it+=1){
        d=*it;
        if (B % d == 0)
        {
            fact[++t] = d;
            while (B % d == 0)
                B /= d;
        }
        if (d > sqrt(B) && B > 1)
        {
            fact[++t] = B;
            B = 1;
        }
    }

    ll sol = A;
    for (int i = 1; i < (1 << t); i++)
    {
        ll nr = 0, prod = 1;
        for (int j = 0; j < t; j++)
            if ((1 << j) & i)
            {
                prod = 1LL * prod * fact[j + 1];
                nr++;
            }

        if (nr % 2) nr = -1;
        else nr = 1;

        sol = sol + 1LL * nr * A / prod;
    }

    fout<<sol<<'\n';
}

int main()
{
    prim.reserve(100000);
    fin>>M;
    erato();
    for (int i = 1; i <= M; i++)
    {
        fin>>A>>B;
        solve();
    }
    return 0;
}