# include<stdlib.h>
# include<stdio.h>
# include<math.h>
#include<string>
# define FIN "pinex.in"
# define FOUT "pinex.out"
# define NMAX 1000000
using namespace std;
long long M, A, B, dv[30];
int np[80000];
bool prim[NMAX];

void ciur() { 
	fill(prim + 2, prim + NMAX, 1);

	for (int i = 2; i < NMAX; i++)
		if (prim[i]) {
			for (int j = 2 * i; j < NMAX; j += i)
				prim[j] = false;
			np[++np[0]] = i;
		}
}
void rez()
{long long nrdiv=0;long long sol;
    long long i=0;
    while (B > 1) {
		i++;
        if (B % np[i] == 0) {
            dv[++nrdiv] = np[i];
            while (B % np[i] == 0)
                B /= np[i];
        }

        if (np[i] > sqrt(B) && B > 1) {
            dv[++nrdiv] = B;
            B = 1;
        }
    }
  long long bin=1<<nrdiv;
sol=A;  
for(int i=1;i<bin;i++)
 {long long nr=0;long long rez=1;
  for (int j=0;j<nrdiv;j++)
   if((1<<j) & i) {rez=1LL*rez* dv[j+1];
                nr++;}
   if(nr%2) nr=-1;
   else nr=1;
   sol=sol+1LL*nr*A/rez;     
        }       
  printf("%lld\n",sol);      
     }     
long long  T;     
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%lld\n",&T);
ciur();
for(;T;T--)
 {scanf("%lld %lld",&A,&B);
    rez();      
     }
    
    return 0;}