#include <fstream>
#include <bitset>
#define dim 1000009

using namespace std;
ifstream in ( "pinex.in" );
ofstream out( "pinex.out" );
long long i, n, j, k, t, a, b, nrdiv, d, v[100], w[100], nr, sol;
bitset < dim+9 > ciur;
long long p[80000];

int main() {
	for ( i=2; i <= dim; i++ )
		if ( !ciur[i] ){
			p[++k]=i;
			for ( j=i; j <= dim; j += i )
				ciur[j]=1;
		}
	for ( in >> t; t--; ){
		in >> a >> b; long long total=0;
		for ( d=1, nrdiv=0; p[d] <= b/p[d] && d <= k; d++  )
			if ( b%p[d] == 0){
				v[++nrdiv]=p[d];
				while ( b%p[d] == 0 )
					b /= p[d];
			}
		if ( b>1 ) v[++nrdiv]=b;
		for ( i=0; i <= nrdiv; i++ ) w[i]=0;
		while ( !w[0] ){
			i=nrdiv;
			while ( w[i] )
				w[i--] = 0;
			w[i]=1;
			if ( w[0] ) break;
			nr=0; sol = 1;
			for ( i=1; i <= nrdiv; i++ )
				if ( w[i] )
					nr++, sol *= v[i];
			if ( nr % 2 ) total += a/sol;
			else total -= a/sol;
		}
		out << a-total << "\n";
	}
	return 0;
}