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

#define maxx 1000000

vector <int> v;
bitset <maxx> seen;
int T , a , b , i , j , aux , k , divs[50];

void Sieve()
{
	int i , j;
	
	v.push_back(2);
	
	for( i = 3 ; i <= maxx ; i += 2 )
		if ( ! seen[i] )
		{
			v.push_back(i);
			for( j = i ; j <= maxx ; j += i );
				seen[i] = true;
		}
		
}
 

void Desc()
{
	//memset( 0 , div , 30 * sizeof(int));
	int i ;
	for( i = 0 ; v[i] * v[i] <= b ; ++i )
		if ( b % v[i] == 0) 
		{
			divs[k++] = v[i];
			while ( b % v[i] == 0 ) b /= v[i];
		}
	if ( b != 1 ) 
		divs[k++] = b;
		
}

ll int solve ()
{
	ll int i , j , act , nr , sol = 0, cnt = 0;
	
	for( i = 1 ; i < (1 << k) ; ++i )
	{
		act = 1;
		cnt = 0;
		for ( j = 0 ; (1 << j) <= i ; ++j )
			if ( (1 << j) & i ) { 
				act *= divs[j],
				cnt++;
			}
		if ( cnt % 2 ) 
			nr = 1;
		else 
			nr =-1;
		sol += nr * ( a / act ); 
	}
	
return sol;
}
	

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