#include <cstdio>
#define nmp 1000050
#define primel 80010
#include <algorithm>
#define f_max 50
#include <cmath>

using namespace std;

bool prmc[nmp];
long long prmll[primel],fact[f_max];
long long a,b;

int m;


void eratosthenes(){
   long long i,j;
   for(i=2;i<nmp;++i){

      if(!prmc[i]){
        for(j=i<<1;j<nmp;j+=i)
             prmc[j]=1;
       prmll[++prmll[0]]=i;
      }
   }
}

void search_prime(){
    long long t=0,d=0;
    while(b>1){
        d++;
        if(b%prmll[d]==0){
            fact[++t]=prmll[d];
            while(b%prmll[d]==0)
                b/=prmll[d];

        }
        if(prmll[d]>sqrt(b) && b>1){
            fact[++t]=b;
          break;
        }
    }
   long long r=a,no,pr;
   int i,j;
   for(i=1;i<(1<<t);i++){
     no=0;
     pr=1;
     for(j=0;j<t;j++){
        if((1<<j)&i){
             pr=1LL*pr*fact[j+1];
             no++;
        }
     }
     if(no%2==1)no=-1;
       else
        no=1;
       r=r+1LL *no* a / pr;
   }
   printf("%lld\n",r);
}

int main()
{

    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    eratosthenes();
    scanf("%d ",&m);
    while(m--){
        scanf("%lld %lld ",&a,&b);
        search_prime();
    }

    return 0;
}