#include<stdio.h>
#include<math.h>
# include <algorithm>
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,crer;

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(){
   freopen("pinex.in","r",stdin);
   freopen("pinex.out","w",stdout);
    prim[1]=2; nr=1; 
	ciur();
    scanf("%lld\n",&n);
    for (l=1;l<=n;l++){
       scanf("%lld %lld\n",&a,&b);
       nr=3100;k=0;card=0; 
	   long long crer=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[i]>sqrt(crer)) 
        {                  
            p[++k]=b;
            b=1;
        }
		   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;
        }
       printf("%lld\n",a-card);
    };
    return 0;
}