(*
Problem		:	gcd
Author		:	whitetooth
Start Time	:	2012-3-23 21:21
Finish Time	:	2012-3-23 21:36
Result		:	
Method		:	Violence
*)
Program T_Gcd;
Var
	t,n,m						:longint;
	ans							:longint;
	
Procedure Init;
Begin
	read(n,m);
	ans:=0;
End;
	
Function Gcd(x,y:longint):longint;
Begin
	if y=0 then exit(x)
	else exit(gcd(y,x mod y));
End;
	
Procedure Main;
Var i							:longint;
Begin
	for i:=m to n do
		if gcd(n,i)>=m then inc(ans);
End;

Procedure Print;
Begin
	writeln(ans);
End;
	
Begin
	Assign(input,'gcd.in'); reset(input);
	Assign(output,'gcd.out'); rewrite(output);
	Read(t);
	For t:=1 to t do
		Begin
			Init;
			Main;
			Print;
		End;
	Close(input); close(output);
End.