#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;
        }
    }
}*/
void ciur() {
     
    fill(ch + 2,ch +500000, 1);
 nr=0;
    for (int i = 2;i<500000; i++)
        if (ch[i]) {
            for (int j = 2 * i; j < 500000; j += i)
                ch[j] = false;
            prim[++nr] = i;
        }
}
int main(){
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    prim[1]=2; nr=1; 
	ciur();
    f>>n;
    for (l=1;l<=n;l++){
        f>>a>>b;
       nr=1;k=0;card=0; 
	   while (b>1){
           if (b%prim[nr]==0) {
                k++;
                p[k]=prim[nr];
                while (b%prim[nr]==0)
                     b=b/p[k];
            }
		   nr++;
        }
        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;
}