const f = 'pinex.in'; g = 'pinex.out';
const max_p = 1000000;
type i64 = int64;
var
	fact : array[0..30] of i64;
	m, a, b : i64;
	fprim : array[0..80000] of longint;
	prim : array[0..max_p] of boolean;
	i1 : longint;

procedure prec ;
	var
		i, j : longint;
	begin
		//for i := 2 to max_p do prim[i] := true;
		fillchar(prim, sizeof( prim ), true );
		for i := 2 to max_p - 1 do begin
			if prim[i]=true then begin
				j := i * 2;
            	while j < max_p do begin
					prim[j] := false;
					j := j + i;
					end;
				inc(fprim[0]);
				fprim[fprim[0]] := i;
				end;
			end;
	end;

procedure solve ;
	var
		i, j : longint;
		sol, t, d : i64;
		nr, prod : i64;
	begin
		t := 0; d := 0;

		while ( b > 1 ) do begin
			inc ( d );
			if ( b mod fprim[d] = 0 ) then begin
				inc( t );
				fact[t] := fprim[d];
				while ( b mod fprim[d] = 0 ) do
					b := b div fprim[d];
				end;
			if ( fprim[d] > sqrt(b) ) and ( b > 1 ) then begin
				inc( t );
				fact[t] := b;
				b := 1;
				end;
			end;

		sol := a;
		for i := 1 to (1 shl t) - 1  do begin
			nr := 0; prod := 1;
			for j := 0 to t - 1 do
				if ( ( 1 shl j ) and i ) > 0 then begin
					prod := 1 * prod * fact[j + 1];
					inc( nr );
					end;
			if nr mod 2 = 1 then nr := -1
							else nr := 1;
			sol := sol + 1 * nr * A div prod ;
			end;
		writeln( sol );
	end;

begin
	assign( input,f ); reset( input );
	assign( output,g ); rewrite( output );
	prec;
	readln( m );
	for i1 := 1 to m do begin
		readln( a, b );
		solve;
		end;
		
end.