#include<cstdio>
#include<bitset>
#include<vector>
#define ll long long
using namespace std;

#define maxx 1001000
#define maxx2 80000
int v[maxx];
bool seen[maxx];
ll int   a , b , divs[30] ;
int T , i , j , k , n;

void Sieve()
{
	int i , j;
	
	v[0]= 2;
	
	//for( i = 2 ; i <= maxx ; i += 2 ) 
		//seen[i] = true;
	
	for( i = 3 ; i <= maxx ; i += 2 )
		if ( seen[i] == false)
		{
			v[n++] = i;
			for( j = i ; j <= maxx ; j += i )
				seen[j] = true;
		}
		
}
 


int solve ()
{
	ll int act , nr , sol = 0, cnt = 0;
	int i , j;
	
	for( i = 0 ; (ll) v[i] * v[i] <= b ; ++i )
		if ( b % v[i] == 0) 
		{
			divs[k++] = v[i];
			for ( ; b % v[i] == 0 ; b /= v[i] ) ;
		}
	if ( b != 1 ) 
		divs[k++] = b , b = 1;
	
	
	for( i = 1 ; i < (1 << k) ; ++i )
	{
		act = 1;
		cnt = 0;
		for ( j = 0 ; j <= k ; ++j )
			if ( (1 << j) & i ) { 
				act *= divs[j],
				cnt++;
			}
		if ( cnt & 1 ) 
			nr = 1;
		else 
			nr =-1;
		sol += 1LL * nr * ( a / act ); 
	}
	
printf("%lld\n",a - sol);
}
	

int main()
{
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	
	scanf("%d",&T);
	
	Sieve();
	
	for( ; T -- ; )
	{
		k = 0;
		scanf("%lld %lld",&a,&b);
		//Desc();
		//printf("%lld\n",a - solve());
		solve();
	}
	
return 0;
}