#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
const int PM=35000;
int NRP=0;
int pr[3800];
int v [PM];
int List[PM];
int st[PM];
int L=0;
int A,B;
void ciur()
{
    int i,j;
    for (i=4;i<=PM;i=i+2)
        v[i]=1;
    for (i=3;i<=PM;i=i+2)
    {
        if (v[i]==0)
        {
            for (j=i*2;j<=PM;j=j+i)
                v[j]=1;
        }
    }
 for (i=2;i<=PM;i++)
 {
     if (v[i]==0)
     {
         NRP++;
         pr[NRP]=i;
     }
 }
}
int s=0;
int s2;
void Back(int i,int k)
{
    if (i>L)
    {
         if (k>0)
         {
            s2=1;
            for (int f=1;f<=L;f++)
            {
                if (st[f]==1)
                {
                    s2*=List[f];
                }
            }
        if (k%2==0)
            s-=A/s2;
        else
            s+=A/s2;
         }
    }
    else
    {
    st[i]=0;
    Back(i+1,k);
    st[i]=1;
    Back(i+1,k+1);
    }

}
void desp()
{
    int i;
    for (i=1;i<=NRP&&B>1;i++)
    {
        if (B%pr[i]==0)
        {
            List[++L]=pr[i];
        while (B%pr[i]==0)
        {B=B/pr[i];}
        }
    }
    if (B>1)
    {
        List[++L]=B;
    }
}
int main()
{
    ifstream in("pinex.in");
    ofstream out("pinex.out");
ciur();
int M;
in>>M;
int i;
for (i=1;i<=M;i++)
{
    L=0;
    s=0;
in>>A>>B;
desp();
Back(1,0);
out<<A-s<<"\n";
}
out.close();
in.close();
return 0;
}