#include <fstream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

#define MAX_SIZE  1000005

using namespace std;

ifstream in ( "pinex.in" );
ofstream out ( "pinex.out" );

int M , A , B , v[MAX_SIZE] , Answer,  p[MAX_SIZE];
vector < long long > divs,divs_nr;
bool used[MAX_SIZE] ,  ciur[MAX_SIZE] ;

void Eratosthene ( void )
{
	int i , j ;
	for ( i = 2 ; i <= MAX_SIZE ; ++i )
		if ( ciur[i] == false )
		{
			for ( j = i+i ; j <= MAX_SIZE ; j+=i )
				ciur[j] = true ;
			divs.push_back(i);
		}
}
void Backtracking ( int k , int N )
{
	int i  ;
	for ( i = v[k-1] +1 ; i <= N ; ++i )
	{ 
		v[k] = i ;
		p[k] = p[k-1] * divs_nr[v[k]];
		if ( k % 2 )
			Answer += A/p[k];
		else
			Answer -= A/p[k];
		if ( k < N )
			Backtracking( k+ 1 , N );
		
	}
	
}

int main ( void )
{
	int i , j ;
	in >> M ; 
	Eratosthene();
	p[0] = 1 ; 
	for ( i = 1 ; i <= M ; ++i )
	{
		in >> A >> B;
		divs_nr.push_back(156);
		int l = sqrtl( B );
		for ( j = 0 ; j < divs.size() && divs[j] <= l ; ++j )
			if ( B % divs[j] == 0 )
			{
				divs_nr.push_back(divs[j]);
				while ( B % divs[j] == 0 )
					B /=divs[j];
			}
			if ( divs_nr.size() == 0 )
			{
				out << A -1 << "\n" ;
				Answer = 0 ;
				continue ;
			}
			if ( B > 1 )
				divs_nr.push_back(B);
		Backtracking ( 1 , divs_nr.size() - 1 );
		out << A - Answer << "\n";
		divs_nr.clear();
		Answer = 0 ;
	}
}