#include<iostream>
#include<fstream>
#include <vector>

#define max 1000000

using namespace std;

int vin[80000];
bool bol[1000000];

int prim ()
{
     int j,k,nr=-1;
     bol[0] = true;
     bol[1] = true;
     for ( j = 2 ; j < max; j++)
         if ( bol[j] == false)
       {  
         for( k = 2 *j ; k < max; k= k + j)
         {
              bol[k] = true;
          }
          nr++;
          vin[nr] = j;
         }
     return nr;
}

int main()
{
    long long pr [30];
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    int M,i,no=0,l,nrdiv, cont2,nrbit;
    long long produs, suma,A,B,cont1;
    in>>M;
    no = prim();
    for (i = 0 ; i< M;i++)
    {
        in>>A>>B;
        nrdiv=0; l = 0;
       /* for ( l = 0 ;  vin[l] < B; l++)
        {
            if ( B % vin[l] == 0 ) 
            {
               pr[nrdiv]=vin[l];
               nrdiv++;  
              // out <<A<<" " <<B<<" "<< vin[l]<< "\n\n";  
            }
        }*/
        if ( B == 1 ) out<<A<<"\n";
         else
   {       while ( B > 1 ) 
        {
              if ( B % vin[l] == 0 ) 
              {
                   pr[nrdiv] = vin [l];
                   nrdiv++;
                   while ( B % vin[l] == 0 ) B /= vin[l];
               }
              if ( B < vin[l] * vin[l] && B > 1 )
              {pr[nrdiv] = B;
              nrdiv++;
              B=1;
              }
              l++;
         }
         
        if ( nrdiv == 0 ) out<<(A - A / B)<<"\n";
        else 
             {     
                   suma= 0;
                   produs =1 ;
                   for (cont1 = 1 ; cont1 < (1 << (nrdiv)); cont1++)
                       {
                       nrbit = 0;
                       produs = 1;
                              for ( cont2 = 0; cont2 < nrdiv ; cont2++)
                              {
                              if (cont1 & ( 1 << cont2)) {
                                                       nrbit++;
                                                       produs =1LL* produs* pr[cont2];
                                                       } 
                              }
                              if ( nrbit % 2 == 0 ) 
                              {
                                   suma = suma - 1LL* A / produs;
                                  // out<<"cont1 "<< cont1 << " cont2 "<< cont2<<" produs "<<produs<<"\n";
                              }
                              else
                              {
                                   suma = suma + 1LL* A / produs;
                                 //  out<<"cont1 "<< cont1 << " cont2 "<< cont2<<" produs "<<produs<<"\n";
                              }
                       }
                       out << (A- suma) << "\n"; 
             }   
    }
}
    in.close();
    out.close();
    return 0;
}