#include<fstream>
#include<algorithm>
using namespace std;

int a[100],v[100],i,j,k,n,x,y,s;

int main()
{
    ifstream f("pietre.in");
    ofstream g("pietre.out");
	a[1]=1;a[2]=2;
	for (i=3;i<=41;i++)
		a[i]=a[i-1]+a[i-2];
	f >> n;
	for (j=1;j<=n;j++)
	{
		f >> x >> y;
		if (y<x)
			swap(x,y);
		for (i=1;i<=41;i++)
			v[i]=0;
		for (i=41;i>=1;i--)
			if (a[i]<=x)
			{
				v[i+1]=1;
				x-=a[i];
			}
		s=0;
		for (i=1;i<=41;i++)
			if (v[i]==1)
			{
				if (i%2==1)
					s=1;
				break;
			}
		if (s==1)
		{
			g << 1 << "\n";
			continue;
		}
		for (i=1;i<=41;i++)
			if (v[i]==1)
			{
				s+=a[i];
				v[i]=0;
			}
		if (s==y)
			g << 2 << "\n";
		else g << 1 << "\n";
	}
	return 0;
}