#include<fstream.h>
ifstream f("pinex.in");
ofstream g("pinex.out");
int a,b,nr,r,x,y,i,m;
int main(){
	f>>m;
	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++;
		}
		g<<nr<<'\n';
		m--;
	}
	g.close(); return 0;
}