#include <iostream>
#include <fstream>
using namespace std;
bool v[1000001];
int a[80000];
int long long b[200], i, q, ok, k, l, p, n, m, fact, j, i1;
/*void gen_ciur()
{
    int i, k;
    for(i=2; i<=m; i++)
    {
        if(v[i]==false)
        {
            a[++p]=i;
            k=i+i;
            while(k<=m){v[k]=true; k+=i;}
        }
    }
}*/
void gen_ciur()
{
    for ( int i = 2; i <= 1000001; ++i )
        v[i] = true;

    for ( int i = 4; i <= 1000001; i += 2 )
       v[i] = false;

   a[++p] = 2;

    for (int i = 3; i <= 1000001; i += 2 )
        if ( v[i] )
        {
            a[++p] = i;

            for (int j = 3 * i; j <= 1000001; j += 2 * i)
                v[j] = false;
        }
}
void descompun(int long long n)
{
    fact=0;
    for(i=1; i<=p&&n>=1LL*a[i]*a[i]; ++i)
    {
        if(n%a[i]==0)
        {

            while(n%a[i]==0) n/=a[i];
            b[fact++]=a[i];
        }
    }
    if(n>1)
    {
        b[fact++]=n;
        n=1;
    }
}
int f(int long long n)
{
    int long long s=0;
    for(i=1; i< (1<<fact); ++i)
    {
        int nrb=0;
        long long prod=1;
        for(j=0; j<fact; ++j)
        {
            if(i&(1<<j))
            {
                nrb++;
                prod*=1LL*b[j];
            }
        }
        if(nrb%2==1) s+=n/prod;
        else s-=n/prod;

    }
    return s;
}
int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");
    fin>>l;
    gen_ciur();
    for(i1=1; i1<=l; i1++)
    {
        fin>>n>>m;
        descompun(m);
        fout<<n-f(n)<<"\n";

    }
    return 0;
}