#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>

using namespace std;
#define MAX 1000000
#define ll long long
ll M;
ll A,B;
ll R;
bool *prim;
int  nrPrime[MAX];
int cntNrPrime = 0;

ll *fact;
int cntFactori = 0;

void ciur()
{
    for(int i=2;i<MAX;i++)
        if(prim[i])
        {
            nrPrime[cntNrPrime++] = i;
            int j = 2;
            while( i * j <= MAX)
            {
                prim[i*j] = false;
                j++;
            }
        }
}

void factori(ll nr)
{
    cntFactori = 0;
    int cnt = 0;
    ll prim = nrPrime[cntFactori];
    ll L = sqrt(nr);
#ifdef DEBUG
    cout<<"factori()"<<endl;
    cout<<nr<<" "<<(int)sqrt(nr)<<endl;
#endif

    while(nr > 1)
    {
#ifdef DEBUG
cout<<prim<<" ";
#endif
#ifdef DEBUG2
    cout<<nr<<" "<<prim<<endl;
#endif

        if(nr % prim == 0)
        {

            fact[cntFactori++] = prim;

            while(nr%prim == 0)
            {
                nr /= prim;
            }
        }

        prim = nrPrime[++cnt];

        if(nr>1 && prim>L)
        {
            fact[cntFactori++] = nr;
            nr = 1;
        }
    }

#ifdef DEBUG
    cout<<endl;
#endif
}

void rezolva()
{
    int combinatii = (1<<(cntFactori)) - 1;

#ifdef DEBUG
cout<<"rezolva()"<<endl;
cout<<cntFactori<<endl;
for(int i=0;i<cntFactori;i++)
    cout<<fact[i]<<" ";
cout<<endl;
cout<<"combinatii:"<<combinatii<<endl;
#endif
    int nr;
    ll prod;
    for(int i=1;i<=combinatii;i++)
    {
        prod = 1;
        nr = 0;

        for(int j=0;j<cntFactori;j++)
            if(i & (1<<j))
            {
                prod *= (ll)fact[j];
                nr++;
            }
#ifdef DEBUG
        cout<<prod<<endl;
#endif

        if(nr%2 == 1)
        {
             R += (ll)A/prod;
        }
        else
             R -= (ll)A/prod;
    }
}

int main()
{    
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    int N;
    scanf("%d", &N);
    
    prim = new bool[MAX];
    memset(prim, true, MAX);
    ciur();

    fact = new ll[cntNrPrime];

    for(int i=0;i<M;i++)
    {
        scanf("%lld %lld", &A, &B);

        factori(B);
        R = 0;
        rezolva();
    }

    delete[] prim;
    delete[] fact;
    return 0;
}