#include <bits/stdc++.h>
#define ll long long
#define PMax 13
#define ValMax 1000001
#define PrimMax 78499

using namespace std;

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

int m;
ll a, b;
ll res;
ll p[PMax];
bool ciur[ValMax];
int prim[PrimMax];

void Ciur()
{
    ciur[0] = 1;
    ciur[1] = 1;
    for ( int i = 2; i * i < ValMax; i++ )
        if ( !ciur[i] )
            for ( int j = i * i; j < ValMax; j += i )
                ciur[j] = 1;
}

void CreazaPrime()
{
    for ( int i = 2; i < ValMax; i++ )
        if ( !ciur[i] )
            prim[++prim[0]] = i;
}

int solve()
{
    ll lg = 0;
    int ind = 1;
    while ( prim[ind] * prim[ind] <= b && b[ind] != 0 )
    {
        int e = 0;
        while ( b % prim[ind] == 0 )
        {
            b /= prim[ind];
            e++;
        }
        if ( e != 0 )
            p[lg++] = prim[ind];
        ind++;
    }
    if ( b > 1 )
        p[lg++] = b;

    ll sol = 0;
    for ( int i = 1; i < (1 << lg); i++ )
    {
        int nr = 0;
        ll prod = 1;
        for ( int j = 0; j < lg; j++ )
        {
            if ( (1 << j) & i )
            {
                nr++;
                prod *= p[j];
            }
        }
        if ( nr % 2 == 0 && prod != 0 ) sol -= (a / prod);
        else sol += (a / prod);
    }
    res = a - sol;

}


int main()
{
    Ciur();
    CreazaPrime();
    fin >> m;
    for ( int i = 1; i <= m; i++ )
    {
        fin >> a >> b;
        solve();
        fout << res << '\n';
    }
    return 0;
}