#include<fstream>
#include<math.h>
using namespace std;
long long x,numitor,nr1,card,a,i,j,k,l,prim[100100],n,nr;
bool ch[1000100];
long long p[100100];
long long b;
void factori()
{
    i=0; double L=sqrt(b); k=0;
    while(b>1)  
    {           
        i++;    
        if(b%prim[i]==0)
        {
            p[++k]=prim[i];
            while(b%p[i]==0)
                b/=prim[i];
       }
        if(b>1 && prim[i]>L) 
        {                  
            p[++k]=b;
            b=1;
        }
    }
}
int main(){
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    for (i=2;i<=100000/2;i++){
        if (ch[i]==false){
            for (j=2;j<=100000/i;j++)
                ch[i*j]=true;
        }
    }
    for (i=2;i<=100000;i++)
        if (ch[i]==false) {
            nr++;
            prim[nr]=i;
        }
    f>>n;
    for (l=1;l<=n;l++){
        f>>a>>b;
       // nr=1;k=0;card=0; L=sqrt(b);
        //while (b>1){
          //  if (b%prim[nr]==0) {
            //    k++;
              //  p[k]=prim[nr];
                //while (b%prim[nr]==0)
                 //     b=b/p[k];
            //}
			//if(b>1 && prim[nr]>L){                   
              //   p[++k]=b;
                // b=1;
			//}
            //nr++;
        //}
		factori();
        for (i=1;i<1<<k;i++){
            x=i;
            numitor=1;
            nr1=0;
            for (j=1;j<=k;j++){
                if (x%2==1){
                    numitor=numitor*p[j];
                    nr1++;
                }
                x=x/2;
            }
            if (nr1%2==1) card=card+a/numitor;
            else card=card-a/numitor;
        }
        g<<a-card<<"\n";
    };
    return 0;
}