#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 ( long long aux=1; aux < (1<<(nrdiv+1)); aux++ ){
			nr=0; sol=1; long long auxx=aux;
			for ( j=0; j < nrdiv; j++ ){
				if ( auxx & 1 )
					nr++, sol *= v[j+1];
				auxx >>= 1;
			}
			if ( nr % 2 ) total += a/sol;
			else total -= a/sol;
		}
		out << (a-total)/2 << "\n";
	}
	return 0;
}