#include<fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int a,b,i,nr,m,r,x,y;
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;
}