#include <stdio.h>
#include <vector>

#define MAX_NO 78501
const int op[] = { -1, 1 };

int prime[ MAX_NO ];
std::vector<long long> fact;

void Eratostene() {
	const int MAX = 1000002;
	const int MAXV = MAX / 2;
	bool *ciur = new bool[ MAXV ]();
	{
		for( int i = 1; 2 * i * ( i + 1 ) <= MAXV; i++ )
			if( !ciur[ i ] ) {
				const int V = 2 * i + 1;
				for( int j = 2 * i * ( i + 1 ); j <= MAXV; j += V )
					ciur[ j ] = 1;
			}
	}

	{
		int nn = 1;
		prime[ 0 ] = 2;
		for( int i = 1; i <= MAXV; i++ )
			if( !ciur[ i ] )
				prime[ nn++ ] = ( i << 1 ) + 1;
	}
	delete[] ciur;
}

int main()
{
	{Eratostene();}


	int q;
	long long x, A;
	FILE *fin = fopen( "pinex.in", "r" );
	FILE *fout = fopen( "pinex.out", "w" );

	fscanf( fin, "%d", &q );
	while( q-- ) {
		fscanf( fin, "%lld %lld", &A, &x );
		for( int i = 0; ( long long )prime[ i ] * prime[ i ] <= x; i++ )
			if( x % prime[ i ] == 0 ) {
				while( x % prime[ i ] == 0 )
					x /= prime[ i ];
	 
				fact.push_back( ( long long )prime[ i ] );
			}
 
		if( x > 1 )
			fact.push_back( x );
		
		long long val;
		long long rez = 0;
		int n = fact.size();
		int right = ( 1 << n ), cate;
		for( int i = 1; i < right; i++ ) {
			val = 1LL;
			cate = 0;
			for( int j = 0; j < n; j++ )
				if( ( i >> j ) & 1 )
					val *= fact[ j ], ++cate;
			rez += op[ cate & 1 ] * ( A / val );
		}
 		fact.clear();
		
 		fprintf( fout, "%lld\n", A - rez );
	}

	fclose( fin );
	fclose( fout );
 	return 0;
}