#include <fstream>
#define nmax 1000005
#define ll long long 
using namespace std;
ifstream fin("pinex.in");
ofstream fout ("pinex.out") ; 
ll i, j, n, B, m, k; 
ll A;
bool v[1000002];
int a[7330000] , d[6330000];
void ciur()
{
	int i , j; 
	for( i = 2; i < nmax; i++)
	{
		if( v[i] == 0 )
			for(j = i + i ; j < nmax; j += i  )
				v[j] = 1;
	}
	for( j = 2; j < nmax; j++ )
		if(v[j] == 0 )
		{
			a[++k] = j; 
			
		}
		

}

ll nrdiv()
{
	ll i , nr = 0, x, ok = 1, ret;
	
	ll sol = 0;
	for( i = 1 ; i <= k ; i++)
	{
		if(B % a[i] == 0)
		{
			d[++nr] = a[i]; 
			

		}
		
	}
	for( i = 1; i < (1<<nr) ;i++)
	{
		x = 1;
		ok = 1;
		for(j = 0 ; j <	nr ; j++)
			if( ( 1 << j ) & i)
			{
				x *= d[ j + 1 ] ;
				ok++;
			}
			ret = A / x ;
		if(ok % 2 == 0 )
			sol += ret;
		else
			sol -= ret;
				
	}
	//fout << sol << '\n' ;
	fout << A - sol <<'\n' ;
	return A - sol ;
}

void calc()
{
	int i;
	
	fin >> m ;
	
	for( i = 1; i <= m; i++)
	{
		fin >> A >> B;
		//fout << A <<  " " << B << '\n'; 
		nrdiv();
		
	}		
		
	
}
int main()
{
	ciur();
	calc();
	fin.close();
	fout.close();
	return 0;
}