#include<fstream.h>
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,A,B,r,x,y,i,nr;
int main(){
	f>>m;
	nr = 0;
	while((m)){
		f>>A>>B;
		nr  = 1;
		for(i = 2;i <= A;++i){
			x = i;y = B;
			while((y)){
				r = x % y;
				x = y;
				y = r;
			}
			if(x == 1) nr = nr +  1;
		}
		g<<nr;
		m-=m;
	}
	g.close();
	return 0;
}