#include<fstream>
#include<vector>
using namespace std;

int m;
long long a, b;
vector<long long> diviz, primes;
bool viz[1000006];

int main(void) {
    ifstream cin("pinex.in");
	ofstream cout("pinex.out");
	
	for (int i=2; i<=1000000; ++i)
	if (viz[i]==0) {
	   primes.push_back(i);	
	   for (int j=2; j*i<=1000000; ++j) viz[i*j]=1;
	}
	
	cin>>m;
	
	for (; m>0; --m) {
	   cin>>a>>b;
	   
	   diviz.clear();
	   
	   for (int i=0; i<primes.size() && b>1 && primes[i]*primes[i]<=b; ++i)
	    if (b%primes[i]==0) {
	       diviz.push_back(primes[i]);
		   while (b%primes[i]==0) b/=primes[i];	
	    }
	    
	   if (b>1) diviz.push_back(b);
	    
	   long long res=0;
	   
	   for (int i=1; i<(1<<diviz.size()); ++i) {
	   	 long long cmmmc=1;
	   	 long long semn=-1;
	   	
	   	 for (int j=0; (1<<j)<=i; ++j)
	   	  if ( (i&(1<<j))!=0 ) { semn*=-1; cmmmc*=diviz[j]; }
	   	  
	   	 res+=semn*(a/cmmmc);
	   }
	   
	   cout<<a-res<<"\n";
    }
	
	return 0;
}