#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long int f[100]={1,1};
long long int absint(int x)
{
	return x>0 ? x:-x;
}
int main()
{
	freopen("infinit.in","r",stdin);
	freopen("infinit.out","w",stdout);
	long long int n,i,j,q=(long long int)(pow(2.0,63.0))-1,mn;
	cin>>n;
	if(n==1)
	{
		printf("4\n");
		return (0);
	}
	unsigned long long int tmp;
	for(i=2;1;i++)
	{
		tmp=f[i-1]+f[i-2];
		if(tmp>q)
		{
			break;
		}
		else
			f[i]=(long long int)(tmp);
	}
	long long int a,b,ans=0,ai,bi;
	for(i=0;i<n;i++)
	{
		cin>>a>>b;
		mn=b;
		for(j=1;j<92;j++)
		{
			if(b-f[j]>=0)
				mn=b-f[j];
			else
			{
				bi=j-2;
				break;
			}
		}
		mn=a;
		for(j=0;j<92;j++)
		{
			if(a-f[j]>=0)
				mn=a-f[j];
			else
			{
				ai=j-2;
				break;
			}
		}
		cout<<f[bi]-f[ai-1]<<'\n';
	}
	return (0);
}