#include <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <algorithm>   
#include <iomanip>   
using namespace std;  
long long a[100][2],b,c,d,l,m,n,maxx,k;
bool bo[100]={false};
int main(void)   
{   
    freopen ("infinit.in","r",stdin);   
    freopen ("infinit.out","w",stdout);   
	a[0][0]=1;
	a[0][1]=1;
	bo[0]=true;
	a[1][0]=1;
	a[1][1]=2;
	bo[1]=false;
	maxx=1;
	for (d=0;d<63;d++)
	{
		maxx*=2;
		if (d==61) maxx--;
		if (d==62) maxx++;
	}
	for (d=2;d<100;d++)
	{
		a[d][0]=a[d-1][0]+a[d-2][0];
		a[d][1]=a[d-1][1]+a[d-2][1];
		bo[d]=!bo[d-1];
		if (a[d][0]>maxx-a[d][1]) break;
	}
	cin>>n;
	for (k=0;k<n;k++)
	{
		cin>>b>>c;
		for (l=0;l<d;l++)
			if ((b>=a[l][1])&&(b<a[l+1][1]))
			{
				if (b==c) 
				{
					if (bo[l]==true) cout<<1<<endl;
						else cout<<0<<endl;
				}
					else 
					{
						for (m=l+1;m<=d;m++)
							if ((c>=a[m][1])&&(c<a[m+1][1])) 
							{
								cout<<a[m][0]-a[l][0]<<endl;
								break;
							}
					}
				break;
			}
	}
    fclose(stdin);   
    fclose(stdout);   
    return 0;   
}