#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()
{
    vector <int> pr;
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    int M,A,B,i,no=0,l,nrdiv,cont1, cont2,suma,s,nrbit,produs;
    in>>M;
    no = prim();
    for (i = 0 ; i< M;i++)
    {
        in>>A>>B;
        nrdiv=0;
        for ( l = 0 ;  vin[l] < B; l++)
        {
            if ( B % vin[l] == 0 ) 
            {
               pr.push_back(vin[l]);
               nrdiv++;  
              // out <<A<<" " <<B<<" "<< vin[l]<< "\n\n";  
            }
        }
        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 *= pr[cont2];
                                                       } 
                              }
                              if ( nrbit % 2 == 0 ) 
                              {
                                   suma -= A / produs;
                                  // out<<"cont1 "<< cont1 << " cont2 "<< cont2<<" produs "<<produs<<"\n";
                              }
                              else
                              {
                                   suma += A / produs;
                                 //  out<<"cont1 "<< cont1 << " cont2 "<< cont2<<" produs "<<produs<<"\n";
                              }
                       }
                       out << (A- suma) << "\n"; 
             }   
             pr.clear();
    }
    in.close();
    out.close();
    return 0;
}