#include<iostream>
#include<fstream>
using namespace std;
int main()
{
	int m,a,b,i,j,c,r;
	ifstream fin("pinex.in");
	ofstream fout("pinex.out");
	fin>>m;
	for(i=1;i<=m;i++)
	{
		c=0;
		fin>>a>>b;
		for(j=1;j<=a;j++)
		{
			while(i%b)
			{
				r=i%b;
				i=b;
				b=i;
				i=r;
			}
			if(i==1)
				c++;
		}
		fout<<c<<endl;
	}
	return 0;
}