#include<iostream>
#include<fstream>
using namespace std;
 ifstream f("pinex.in");
 ofstream g("pinex.out");
 int fn(long c,long d)
 {int i,min;
 if(c<d)
	 min=c;
 else
	 min=d;
 for(i=2;i<=min;i++)
	 if(c%i==0&&d%i==0)
		 return 0;
	 return 1;
 }
long fun(long a,long b)
 {
	 long i,nr=0;
	 for(i=1;i<=a;i++)
		 if(fn(i,b))
			 nr++;
		 return nr;
}
int main()
{long n,x,y;
f>>n;
while(n)
{f>>x>>y;
n--;
g<<fun(x,y)<<"\n";
}
f.close();
g.close();
return 0;
}